Варианты возможных вариантов генотипов кошек

[Lida298]

Мы работаем над одним сложным проектом, а именно программа для подсчёта процента возможных генотипов кошек. Мы знаем биологию, но упёрлись в проблему в математической части. Мы хотели бы попросить вас совета.
Допустим у нас есть генотип окраса Черепаховой кошки -
Ww SS Oo aa Dd В зависимости от окраса буквы могут быть как и большие, так и маленькие, например такой ww ss oo aa Dd, а может Ww Ss OO AA dd и тд.
Нужно подсчитать все возможные варианты гамет с этими генами (В гамете может быть только 1 случайный ген из пары)
Если генотип кошки: ww Ss oo aa dd
То её гаметы будут выглядеть так:
wSoad или wsoad
(Порядок написания букв важен)
Но это лёгкий вариант, при более сложном генотипе вариантов возможных гамет очень много.
Не буду углубляться в биологию, а объясню на примере задачи:

Генотип окраса кошки: Ww SS Aa Oo Dd

Цель: узнать все возможное варианты генотипа гамет кошки. Не количество вариантов, а именно все варианты которые могут выпасть.

Генотип гаметы: это набор из 5 генов(букв) выбранных случайно из пар вышенаписанного генотипа кошки.
Например wSaOD, или WSaod и так далее.



Мы пытались подобрать формулу из школьной программы комбинаторики, но увы это не привело к желаемому результату.
Мы создаём программу, которая будет считать все возможное варианты гамет у той, или иной особи.
Нам необходимо вывести алгоритм действий для подсчёта всех возможных гамет у кошки, того, или иного окраса исходя из данных её генотипа. Подскажите, пожалуйста, варианты решения нашей проблемы (со стороны программирования мы разберемся сами)

[Pphantom]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
по следующим причинам:

- отсутствует внятная формулировка условия задачи;
- отсутствуют собственные содержательные попытки решения задачи;
- опрос уберите.
- слово "зигота" в русском языке записывается именно так.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[GAA]

Тема перемещена из форума «Карантин» в форум «Биология и Медицина»

Не понял задачу. Возможно, в разделе БиМ Вам помогут с постановкой задачи.
Если есть «два варианта одного гена» (две аллели [два аллеля]), то для 5 получим $3^5$. Если учитывать порядок, т.е. считать, что $Aa$ и $aA$ различаются (обычно так не принято), то $4^5$.
Если «три варианта одного гена» (три аллели [три аллеля]), то для 5 получим $6^5$.
Если одни «гены» имеют две модификации, пусть их будет $k$, а другие — 3 модификации, пусть их будет $m$, то получим $3^k6^m$, где $k+m=5$.

-- Fri 21.05.2021 20:56:14 --

Lida298 в сообщении #1519408 писал(а):

Мы пытались подобрать формулу из школьной программы комбинаторики, но увы это не привело к желаемому результату.

Если вопрос о формулах. Пусть у нас $n$ «вариантов гена». Тогда для подсчета числа вариантов можно воспользоваться числом сочетаний с повторениями: $\bar C_n^2=\frac {(n+1)!} {2!(n-1)!}$. Если две аллели [два аллеля], то $\bar C_2^2=3$; если три, то $\bar C_3^2=6$.

-- Fri 21.05.2021 20:59:15 --

Дальше используем правило «умножения».

Lida298 в сообщении #1519408 писал(а):

Цель: узнать все возможное варианты генотипа гамет кошки. Не количество вариантов, а именно все варианты которые могут выпасть.

Угадывается задача перечисления. В основе такого перечисления будет лежать перечисление числа сочетаний с повторениями.

[svv]

Я понял задачу так.

Дан список из $n$ пар элементов: $(a_1,b_1), (a_2,b_2), ... , (a_n,b_n)$
Например: $\textsf{(W,w), (S,S), (O,o), (a,a), (D,d)}$.

В некоторых парах элементы совпадают: $a_2=b_2, \; a_4=b_4$
В других парах элементы не совпадают: $a_1\neq b_1, \; a_3\neq b_3, \; a_5\neq b_5$

Составим из исходного списка новый список, произвольным образом выбрав из каждой пары по одному элементу. Это можно сделать разными способами, например:
$a_1, b_2, b_3, a_4, a_5$, то есть $\textsf{W,S,o,a,D}$
$a_1, a_2, b_3, a_4, a_5$, то есть $\textsf{W,S,o,a,D}$
Так как $a_2=b_2$, эти два списка совпадают.
$a_1, b_2, b_3, a_4, b_5$, то есть $\textsf{W,S,o,a,d}$
А это действительно новый вариант.

Сколько различных вариантов списков можно так получить из исходного? Очевидно, $2^k$, где $k$ — число пар с различными элементами в исходном списке.
Более сложная задача: как алгоритмически сформировать и перечислить все $2^k$ различных вариантов?

[Lida298]

svv в сообщении #1519472 писал(а):

Я понял задачу так.

Дан список из $n$ пар элементов: $(a_1,b_1), (a_2,b_2), ... , (a_n,b_n)$
Например: $\textsf{(W,w), (S,S), (O,o), (a,a), (D,d)}$.

В некоторых парах элементы совпадают: $a_2=b_2, \; a_4=b_4$
В других парах элементы не совпадают: $a_1\neq b_1, \; a_3\neq b_3, \; a_5\neq b_5$

Составим из исходного списка новый список, произвольным образом выбрав из каждой пары по одному элементу. Это можно сделать разными способами, например:
$a_1, b_2, b_3, a_4, a_5$, то есть $\textsf{W,S,o,a,D}$
$a_1, a_2, b_3, a_4, a_5$, то есть $\textsf{W,S,o,a,D}$
Так как $a_2=b_2$, эти два списка совпадают.
$a_1, b_2, b_3, a_4, b_5$, то есть $\textsf{W,S,o,a,d}$
А это действительно новый вариант.

Сколько различных вариантов списков можно так получить из исходного? Очевидно, $2^k$, где $k$ — число пар с различными элементами в исходном списке.
Более сложная задача: как алгоритмически сформировать и перечислить все $2^k$ различных вариантов?

Верно, крайнее сообщение описвает нашу проблему

[GAA]

Тогда это не о кошках, и вообще не о цветах
http://www.nsmu.ru/student/pr_education ... 20geni.pdf

Цитата:

Каждый ген может существовать в двух или более альтернативных формах, которые называются аллелями. Так, у кошки ген, контролирующий длину шерсти, представлен в двух формах: аллеля L, дающего короткую шерсть, и l — длинную.
Известны три аллеля гена, контролирующего рисунок: Т^a — абиссинский тэбби, Т — тигровый тэбби и t^b — мраморный, или пятнистый, тэбби.

Вообще, у многих животных часть генов, контролирующих окраску шкуры имеет более двух аллелей.
МНОЖЕСТВЕННЫЙ АЛЛЕЛИЗМ. ВЗАИМОДЕЙСТВИЕ АЛЛЕЛЬНЫХ ГЕНОВ (цвет глаз у дрозофилы, мех кролика — более 3 аллелей.)

Upd Бородин Павел Михайлович "Кошки и гены" третье издание 2011. Можно посмотреть.

[PETIKANTROP]

Абсолютно согласна с GAA. Если аллелей данного гена всего два (пара), то число сочетаний с повторениями =3 ( Ww, WW, ww). Если присутствует множественный аллелизм (непара- a1,b1,c1,...- такое наблюдается в окраске шерсти или наследовании группы крови), то расчет сочетаний производится по формуле

GAA в сообщении #1519452 писал(а):

$\bar C_n^2=\frac {(n+1)!} {2!(n-1)!}$

Затем результаты сочетаний всех генов перемножаются и получаем количество вариантов геномов.

[Lida298]

GAA в сообщении #1519479 писал(а):

Тогда это не о кошках, и вообще не о цветах
http://www.nsmu.ru/student/pr_education ... 20geni.pdf

Цитата:

Каждый ген может существовать в двух или более альтернативных формах, которые называются аллелями. Так, у кошки ген, контролирующий длину шерсти, представлен в двух формах: аллеля L, дающего короткую шерсть, и l — длинную.
Известны три аллеля гена, контролирующего рисунок: Т^a — абиссинский тэбби, Т — тигровый тэбби и t^b — мраморный, или пятнистый, тэбби.

Вообще, у многих животных часть генов, контролирующих окраску шкуры имеет более двух аллелей.
МНОЖЕСТВЕННЫЙ АЛЛЕЛИЗМ. ВЗАИМОДЕЙСТВИЕ АЛЛЕЛЬНЫХ ГЕНОВ (цвет глаз у дрозофилы, мех кролика — более 3 аллелей.)

Upd Бородин Павел Михайлович "Кошки и гены" третье издание 2011. Можно посмотреть.

Спасибо, нам извесна эта информация, чтобы не усложнять мы не учитывали это в посте.

-- 21.05.2021, 23:56 --

PETIKANTROP в сообщении #1519483 писал(а):

Абсолютно согласна с GAA. Если аллелей данного гена всего два (пара), то число сочетаний с повторениями =3 ( Ww, WW, ww). Если присутствует множественный аллелизм (непара- a1,b1,c1,...- такое наблюдается в окраске шерсти или наследовании группы крови), то расчет сочетаний производится по формуле

GAA в сообщении #1519452 писал(а):

$\bar C_n^2=\frac {(n+1)!} {2!(n-1)!}$

Затем результаты сочетаний всех генов перемножаются и получаем количество вариантов геномов.

это понятно, но нам нужно не количество, а именно все возможные варианты гамет

[Geen]

А это всё на одной хромосоме, вообще?

[GAA]

Lida298 в сообщении #1519486 писал(а):

это понятно, но нам нужно не количество, а именно все возможные варианты гамет

Если всем пренебречь, то это все числа от 0b до $2^k$b, где $k$ —число различных пар.

-- Sat 22.05.2021 00:20:32 --

Вместо цифр можно подставить соответствующие буквы, но с цифрами быстрее и удобней.

-- Sat 22.05.2021 00:42:24 --

PETIKANTROP, тут вопрос о типах гамет. Я сначала не понял о чём вопрос. Но после упрощения и проблемы нет: можно просто пять списков перемножить.

[wrest]

Lida298 в сообщении #1519486 писал(а):

это понятно, но нам нужно не количество, а именно все возможные варианты гамет

Перевожу вам что уже сказано выше:

GAA в сообщении #1519489 писал(а):

Если всем пренебречь, то это все числа от 0b до $2^k$b, где $k$ —число различных пар.

Там, правда, должно быть так "это все числа от $0_2$ до $(2^k-1)_2$", ну не суть. Одним меньше, одним больше

По сути у вас сколько-то двоичных разрядов (столько сколько пар разных генов, т.е. где есть выбор). Допустим таких три, тогда вариантов $2^3=8$
Обычно их перебирают так.
$000_2=0_{10}$
$001_2=1_{10}$
$010_2=2_{10}$
$011_2=3_{10}$
$100_2=4_{10}$
$101_2=5_{10}$
$110_2=6_{10}$
$111_2=7_{10}$
Справа номер варианта (нумерация с нуля) в десятичной системе счисления, а слева -- представление этого номера в двоичной системе счисления. Допустим ноль это левый символ из пары, а единица - правый. Тогда скажем Ww Ss Oo перебираются так
000=WSO (три нуля - три левых символа)
001=WSo
010=WsO
011=Wso
100=wSO
101=wSo
110=wsO
111=wso (три единицы - три правых символа)
Если у вас там скажем вклиниваются одинаковые пары, например Ww aa Ss DD Oo то перебирать все равно $2^3=8$ вариантов гамет т.к. гены a и D не меняются и есть в любой гамете, а меняется только три гена Ww, Ss и Oo:
000=WaSDO
001=WaSDo
010=WasDO
011=WasDo
100=waSDO
101=waSDo
110=wasDO
111=wasDo

Понятно вам, сможете это запрограммировать? Так вы можете сделать взаимно-однозначное соответствие номера варианта и соответствующего ему набора. Причем никаких рекурсий, все вычисляется "напрямую", прямо из номера.

[PETIKANTROP]

Geen в сообщении #1519487 писал(а):

А это всё на одной хромосоме, вообще?

Нет. А ген красного (рыжего) цвета, определяющий "черепаховость", еще и сцеплен с полом (с Х хромосомой).
wrest
Как это учесть?

[Lida298]

PETIKANTROP в сообщении #1519513 писал(а):

А ген красного (рыжего) цвета, определяющий "черепаховость", еще и сцеплен с полом (с Х хромосомой).
wrest
Как это учесть?

Мы учитываем это в других таблицах, (вместо второй 0 пишем Y, и оно работает как нужно) сейчас в биологию не стоит лезть, нам нужно именно математическое решение, с части биологии мы всё знаем (в программе чтобы не усложнять мы не будем учитывать вариации гена Т. А L будет считаться отдельно

-- 22.05.2021, 08:26 --

wrest в сообщении #1519494 писал(а):

...

Спасибо большое, мы попробуем сделать именно так:)

[GAA]

wrest в сообщении #1519494 писал(а):

Там, правда, должно быть так "это все числа от $0_2$ до $(2^k-1)_2$", ну не суть. Одним меньше, одним больше

wrest, спасибо! Я бы попробовал выкрутиться и сказать, что верхняя граница цикла не включается (увеличиваем в конце цикла и в случае равенства не переходим к началу цикла). Но на самом деле я думал о другом. Я сначала подумал, если число генов мало, то можно перебирать в регистре SSE/AVX. Но по сравнению с выводом результата сам перебор в любом случае займёт времени намного меньше. Поэтому, пока нет понимания задачи, нет и смысла продумывать реализацию.
Сразу ограничивать задачу случаем двух вариантов гена мне было странно. Ведь и при меньших ограничениях не видно проблем, а попытка обобщить приведёт к необходимости переделки алгоритма.

[Geen]

Lida298 в сообщении #1519518 писал(а):

Мы учитываем это в других таблицах

Если гены лежат на одной хромосоме, то гамет две - какие именно выясняется генотипированием конкретной кошки...

Честно говоря, я так и не понял что дано в задаче.