АвторТема: yImputer - Web-приложение для предсказания STR-маркеров  (Прочитано 2831 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Daemon2017Автор темы

  • Сообщений: 2159
  • Страна: ru
  • Рейтинг +1045/-18
  • Y-ДНК: R1a-Y35174
  • мтДНК: V7-a2a2a2b*
Добрый вечер, коллеги!

Мне всегда было интересно узнать, возможно ли предсказывать неизвестные STR по известным. Например, если у меня есть только Y67-тест, то насколько точным будет предсказание для него Y111?
С этим вопросом я поставил себе фитнес-цель на декабрь: узнать, насколько это возможно. И я узнал - это возможно и с весьма сносной точностью  :)

Репозиторий: https://github.com/Daemon2017/yImputer
Адрес развернутого приложения: http://185.86.145.42:8080 - это API, никакой Web-морды нет и не будет, т.к. мороки много, а потребителей мало.

Как пользоваться.
1) скачайте себе Postman'а https://www.postman.com/downloads/?utm_source=postman-home
2) перейдите по ссылке https://raw.githubusercontent.com/Daemon2017/yImputer/master/yImputer.postman_collection.json и нажмите Ctrl+S, чтобы сохранить JSON-файл с коллекцией запросов
3) откройте Postman'а и импортируйте в него коллекцию с помощью Ctrl+O
После этого, на вкладке Collections у Вас появится коллекция yImputer с двумя запросами (requests):

Далее возможно 2 взаимодействия:
4а) JSON Endpoint. На вкладке Body нужно разместить массив из JSON'ов (от 1 до сотен штук) в формате <"имя_маркера":значение_маркера> в любой последовательности. Например, для одного 12-маркерного случая:
[
    {
        "DYS393": 13,
        "DYS390": 23,
        "DYS19": 14,
        "DYS391": 10,
        "DYS385a": 14,
        "DYS385b": 14,
        "DYS426": 11,
        "DYS388": 14,
        "DYS439": 11,
        "DYS389I": 12,
        "DYS392": 11,
        "DYS389II": 28
    }   
]
После чего требуется нажать синюю кнопку Send в правой верхней части - спустя пару мгновений справа появится ответ, содержащий предсказанные 111 маркеров в стандартном FTDNA'шном порядке:

4б) CSV Endpoint. На вкладке Body в столбце VALUE нужно навести курсор на текущее имя файла и, когда появится значок крестика, следует нажать на него - появится кнопка Select Files. Нажатие на нее приведет к открытию диалогового окна, где нужно указать путь до CSV-файла, содержащего гаплотипы (от 1 до сотен штук). Пример содержимого CSV-файла для 12-маркерного гаплотипа:
DYS393,DYS390,DYS19,DYS391,DYS385,DYS426,DYS388,DYS439,DYS389I,DYS392,DYS389II
13,23,14,10, 14-14,11,14,11,12,11,28
Вот полный набор STR'ов для заголовка таблицы:
DYS393;DYS390;DYS19;DYS391;DYS385;DYS426;DYS388;DYS439;DYS389I;DYS392;DYS389II;DYS458;DYS459;DYS455;DYS454;DYS447;DYS437;DYS448;DYS449;DYS464;DYS460;Y-GATA-H4;YCAII;DYS456;DYS607;DYS576;DYS570;CDY;DYS442;DYS438;DYS531;DYS578;DYF395S1;DYS590;DYS537;DYS641;DYS472;DYF406S1;DYS511;DYS425;DYS413;DYS557;DYS594;DYS436;DYS490;DYS534;DYS450;DYS444;DYS481;DYS520;DYS446;DYS617;DYS568;DYS487;DYS572;DYS640;DYS492;DYS565;DYS710;DYS485;DYS632;DYS495;DYS540;DYS714;DYS716;DYS717;DYS505;DYS556;DYS549;DYS589;DYS522;DYS494;DYS533;DYS636;DYS575;DYS638;DYS462;DYS452;DYS445;Y-GATA-A10;DYS463;DYS441;Y-GGAAT-1B07;DYS525;DYS712;DYS593;DYS650;DYS532;DYS715;DYS504;DYS513;DYS561;DYS552;DYS726;DYS635;DYS587;DYS643;DYS497;DYS510;DYS434;DYS461;DYS435
Такой документ Вы легко можете состряпать сами, копируя гаплотипы из проектов FTDNA :)
Обратите внимание, что CSV=Comma Separated Value, т.е. "том, разделенные запятыми", но в MS Excel есть старинный дефект, из-за которого, без дополнительных донастроек, действие "Меню->Экспорт->Изменить тип файла->CSV" приведет к сохранению файла, где разделителем будет не запятая, а точка с запятой!

На этот случай, в API предусмотрена возможность изменения разделителя, который можно задать аргументом в адресной строке Postman'а:
/predict_csv?sep=;
/predict_csv?sep=,
/predict_csv?sep=.
В целом, можно использовать любой разделитель - должно работать.
Но у MS Excel есть еще один прикол: записи в формате "7-9" он будет считать днем и месяцем даты, превращая их в 07.09.2022. Запись "7-7-7" он превратит в 07.07.2007. Так что лучше пользоваться Google Таблицами: https://docs.google.com/spreadsheets/u/0/
Когда и файл, и разделитель указаны, можно нажимать кнопку Send - Вы получите ответ с предсказанными STR в формате FTDNA, но без дефисов между палиндромами:


Ограничения:
- не умеет работать с гиперпалиндромными палиндромами. Т.е. если Ваш DYS385 состоит не из 2 частей (11-14), а из 3 частей (11-14-15), то я предлагаю подставлять в DYS385a наименьшее значение, а в DYS385b - наибольшее. Это даст наилучший результат, т.к. алгоритм обучался именно так. Аналогично с DYS464 - если у Вас он состоит не из 4 частей, а из 6, то надо брать 2 наименьших и 2 наибольших значения.
- не умеет работать с палиндромностью привычно непалиндромных маркеров. Насколько я помню, DYS19 любит запалиндромиться где-то у каждого 1000-го. Попробуйте подставлять среднее значение маркеров, т.е. (17+15)/2=16
- не умеет работать с нулевыми маркерами - к таким относится DYS425 https://www.familytreedna.com/groups/null-425/about/background и некоторые другие. Алгоритм не обучался на таких ситуациях, так что наличие 0 на месте одного из маркеров может навредить точности. Попробуйте найти ближайшего родича с ненулевым значением и взять его значение.
- алгоритм обучался на современных образцах, так что при попытке использовать его на дДНК, скорее всего, получится мусор

Применение:
- если Вам нужно построить древо STR для нескольких десятков наборов, но среди них, в основном, Y67 и очень мало Y111, то хорошей идеей будет попытаться импутировать 67 до 111, а уже потом строить древо После переоценки качества, стало очевидно, что для точного предсказания Y111, недостаточно Y67 - нужно около 90 маркеров
- если Вам попался очень интересный образец, но он сделан не в FTDNA (допустим, какая-нибудь 17 или 27-маркерная панель) и потому его нельзя задействовать в построении древа, то можно попробовать импутировать его, откинув наименее предсказуемые маркеры
- YFull прочитала 87.5% STR из моего BigY500 и 95% STR из моего WGS Dante Labs - возможно, что алгоритм можно применить для того, чтобы каждому образцу предсказывать 100% маркеров и использовать их при сравнении или оценке TMRCA по STR

Сервис размещен в VK Cloud'е до начала весны, а дальше посмотрим.
Исходный код размещаю под GNU GPL: пользуйтесь, кто хочет. Если будете создавать форк, дорабатывать код и укажете авторство, то буду очень благодарен :))

Если есть пожелания и предложения - пишите, попробую воплотить.
« Последнее редактирование: 20 Декабрь 2022, 09:35:01 от Daemon2017 »

Оффлайн Daemon2017Автор темы

  • Сообщений: 2159
  • Страна: ru
  • Рейтинг +1045/-18
  • Y-ДНК: R1a-Y35174
  • мтДНК: V7-a2a2a2b*
20.12.2022 Вчера по пьяни разместил неверную оценку качества, исправляю. Дело в том, что импутация - это регрессия, а не классификация, т.е. применять классификационные методы оценки качества (F1) не вполне уместно. Заменил F1 на R^2. Результаты не такие радужные, зато честные.

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

В полученном алгоритме переобучение почти отсутствует: даже если соотношение обучающих данных и незнакомых данных равно 1:1, то точность падает не более чем на 4-6%. Такое отклонение обусловлено скорее выбросами и неполнотой самой выборки, нежели переобучением.

Доля обучающей выборки   R^2 на обучающей   R^2 на проверочной
0,25   0,8844   0,8417
0,33   0,8815   0,8367
0,5   0,881   0,8355
0,66   0,8838   0,8298
0,75   0,8841   0,821
https://docs.google.com/spreadsheets/d/1jKHjpMryL5PuAw3oJlyakPTnlA1YsLDZp2uSidOFUG0/edit?usp=sharing

Точность. Если потерять 25% STR (т.е. останется что-то около 83 штук), то восстановить 111 можно с вполне сносной точностью.

Процент потерь   R^2   Эквивалент наличия числа STR
0,89   -0,1103   12,21
0,775   0,0747   24,975
0,67   0,2666   36,63
0,59   0,4079   45,51
0,5   0,5573   55,5
0,4   0,7042   66,6
0,34   0,7824   73,26
0,25   0,8803   83,25
0,2   0,9223   88,8
0,15   0,9555   94,35
0,1   0,9795   99,9
0,05   0,9951   105,45
https://docs.google.com/spreadsheets/d/1_nKPXWHuLkCXN1KG22gd-y36fD4NFvBnlKfUEKfL4Y8/edit?usp=sharing

« Последнее редактирование: 20 Декабрь 2022, 15:03:54 от Daemon2017 »

Оффлайн Daemon2017Автор темы

  • Сообщений: 2159
  • Страна: ru
  • Рейтинг +1045/-18
  • Y-ДНК: R1a-Y35174
  • мтДНК: V7-a2a2a2b*
Алгоритм подготовки данных выглядит следующим образом:
- удаляем все образцы, где менее 111 маркеров - в выборке остается 51к образцов;
- разделываемся с непрочитанными/выпавшими значениями (DYS425 и пр.): просто удаляем их, т.к. они создают выбросы в выборке. Пытаться предсказывать выпадение маркера - дурная идея;
- разделываемся с привычными палиндромами ('CDY', 'DYF395S1', 'DYS385', 'DYS413', 'DYS459', 'YCAII', 'DYS464'): для привычно 2-составных берем наименьше и наибольшее значение, а для привычно 4-составных - 2 наименьших и 2 наибольших. Это решает и проблему мультипалиндромности: из 3-составного палиндрома мы делаем 2-составный, а из 6-составного - 4-составный;
- разделываемся с непривычными палиндромами (DYS425, DYS19 и пр.): просто удаляем их, т.к. не ясно, что с ними делать - усреднять? брать наименьшее/наибольшее?.

Переходим к обучению. Модель регрессионной импутации включает в себя 111 подмоделей, каждая из которых учится предсказывать значение 1 маркера на основании доступной информации о 110 остальных маркерах. Предсказание выполняется последовательно, причем все ранее предсказанные маркеры используются для предсказания последующих маркеров. Как показала практика, лучше всего сперва предсказывать наиболее предсказуемые маркеры, а затем, имея сведения о них, приступать к предсказанию наименее предсказуемых маркеров. Эмпирически выявлен следующий порядок предсказуемости маркеров (по убыванию предсказуемости):
'DYS472', 'DYS436', 'DYS575', 'DYS435', 'DYS590', 'DYS494', 'DYS632', 'DYS490', 'DYS593', 'DYS425', 'DYS641', 'DYS454', 'DYS434', 'DYS450', 'DYS455', 'DYF395S1b', 'DYS726', 'DYS578', 'DYS426', 'YCAIIa', 'DYS531', 'DYS438', 'DYS459a', 'DYS594', 'DYS640', 'DYF395S1a', 'DYS636', 'DYS568', 'DYS392', 'Y-GGAAT-1B07', 'DYS565', 'DYS459b', 'DYS638', 'DYS716', 'DYS492', 'YCAIIb', 'DYS617', 'DYS587', 'DYS388', 'DYS462', 'DYS717', 'DYS589', 'DYS413b', 'DYS445', 'DYS393', 'DYS572', 'DYS487', 'DYS437', 'DYS556', 'DYS463', 'DYS495', 'DYS511', 'DYS497', 'DYS561', 'DYS464a', 'DYS540', 'DYS485', 'DYS464b', 'DYS525', 'DYS448', 'DYS389I', 'DYS537', 'DYS461', 'DYS19', 'DYS385a', 'DYS643', 'DYS441', 'DYF406S1', 'DYS413a', 'DYS464d', 'DYS505', 'DYS452', 'DYS464c', 'DYS520', 'Y-GATA-H4', 'DYS391', 'DYS522', 'DYS385b', 'DYS513', 'DYS533', 'DYS510', 'DYS390', 'DYS635', 'DYS552', 'DYS607', 'DYS389II', 'DYS460', 'DYS442', 'DYS446', 'DYS447', 'DYS557', 'DYS715', 'DYS504', 'Y-GATA-A10', 'DYS444', 'DYS532', 'DYS549', 'DYS456', 'DYS439', 'DYS481', 'DYS650', 'DYS458', 'DYS534', 'DYS570', 'DYS714', 'DYS576', 'DYS712', 'DYS449', 'CDYa', 'CDYb', 'DYS710'

Я исследовал несколько наиболее распространенных регрессоров по 2 критериям:
1) точность (R^2) в ситуации, когда отсутствует 25% маркеров, т.е. предсказываем 111 маркеров по 83 имеющимся;
2) время обучения.
Получилась следующая картина:

Регрессор   R^2 при 0,25 потерь   Время обучения (мин)
DecisionTreeRegressor   0,8803   4,2
RandomForestRegressor   0,8837   6,77
ExtraTreesRegressor   0,8438   3,21
GradientBoostingRegressor   0,619   39,37
XGBRegressor   0,1768   3,98
BayesianRidge   0,04   1,64
AdaBoostRegressor   0,4347   22,5
KNeighborsRegressor   0,9255   0,04
https://docs.google.com/spreadsheets/d/1dwkG_tjrOA7swpxLFxXqOJyDUgCHJo5_NDaWmNrx6NE/edit?usp=sharing

Лучше всех себя показал метод ближайших соседей: R^2=0.93. Но у него есть серьезный изъян: формально он обучается очень быстро, но т.к. алгоритм имеет очень большую алгоритмическую сложность (при предсказании каждого маркера, 110 остальных маркеров последовательно сравниваются со всеми 51к образцов в выборке, т.е. выполняется 5.5ккк сравнений), то работа по предсказанию 50к образцов занимает неприлично большое время - около 30 минут на 16-ядерной машине! Для сравнения, у самого медленного конкурента эта деятельность занимает 30 секунд. По этой причине, выбор пал на метод дерева принятия решений - он имеет точность, сопоставимую с точностью метода случайного леса, но его обучение требует более чем в 1.5 раза меньше времени.
« Последнее редактирование: 20 Декабрь 2022, 15:23:00 от Daemon2017 »

Оффлайн Srkz

  • Сообщений: 8464
  • Страна: ru
  • Рейтинг +4815/-3
  • Y-ДНК: N-L1025 Y64023
  • мтДНК: U4a1-a C16134T
Я, конечно, не знаю сути алгоритма (upd появилось его описание ) ). Но если порассуждать, как вообще может выглядеть импутация с 67 маркеров на 111?
1) строим дерево по 111-маркерным гаплотипам
2) смотрим, на какой узел попадает наш 67-маркерный гаплотип
3) предполагаем, что остальные маркеры у него аналогичны другим гаплотипам этого узла.

Если наш гаплотип попадает сразу в несколько узлов, получаем неоднозначный результат (гомоплазия). Если недостающие до 111 маркеры у гаплотипов этого узла расходятся, тоже получаем неоднозначность. В обоих случаях либо выбираем наиболее частый вариант, либо показываем несколько вариантов с указанием процентной вероятности.

Возможности извлечь из данных более точную и подробную информацию не вижу. Но тогда выходит, что импутация не даёт возможности построить более хорошее дерево, или вообще как-то улучшить предикцию для нашего 67-маркерного гаплотипа, раз мы вынуждены отталкиваться от уже существующего древа. Если же действовать без построения дерева, а по общей частотности, то это должно давать более плохую предикцию, по-моему.
« Последнее редактирование: 21 Декабрь 2022, 07:47:03 от Srkz »

Оффлайн Srkz

  • Сообщений: 8464
  • Страна: ru
  • Рейтинг +4815/-3
  • Y-ДНК: N-L1025 Y64023
  • мтДНК: U4a1-a C16134T
Если же действовать без построения дерева, а по общей частотности, то это должно давать более плохую предикцию, по-моему.
Просто, допустим, мы натравили нейросеть на массив значений стр-маркеров. Чтобы делать правильные предикции, она должна находить "сцепки" - "с таким-то значением маркера А обычно идут такие-то значения маркера Б". Чем больше сцепок найдётся, тем лучше результат. Но нахождение всех сцепок ведь и будет аналогично построению правильного дерева. Если, конечно, мы считаем разные маркеры мутирующими независимо. Если же между ними реально существует какая-то связь, то тогда нейросеть может быть лучше дерева.

Оффлайн Semargl

  • "El sueño de la razón produce monstruos" ©
  • Модератор
  • *****
  • Сообщений: 5994
  • Страна: ru
  • Рейтинг +4192/-5
  • www.semargl.me
    • www.semargl.me
  • Y-ДНК: R1a [CTS3402+]
  • мтДНК: U4a2g
Но нахождение всех сцепок ведь и будет аналогично построению правильного дерева.
Полностью согласен.

Оффлайн Daemon2017Автор темы

  • Сообщений: 2159
  • Страна: ru
  • Рейтинг +1045/-18
  • Y-ДНК: R1a-Y35174
  • мтДНК: V7-a2a2a2b*
Я, конечно, не знаю сути алгоритма. Но если порассуждать, как вообще может выглядеть импутация с 67 маркеров на 111?
1) строим дерево по 111-маркерным гаплотипам
2) смотрим, на какой узел попадает наш 67-маркерный гаплотип
3) предполагаем, что остальные маркеры у него аналогичны другим гаплотипам этого узла.

Если наш гаплотип попадает сразу в несколько узлов, получаем неоднозначный результат (гомоплазия). Если недостающие до 111 маркеры у гаплотипов этого узла расходятся, тоже получаем неоднозначность. В обоих случаях либо выбираем наиболее частый вариант, либо показываем несколько вариантов с указанием процентной вероятности.
Да, все так: это один из вариантов. Условно, я бы назвал его макро-импутацией, т.е. мы берем весь доступный гаплотип и, с помощью поиска по древу или N-ближайших соседей, находим его филогенетическую родню, после чего берем от нее недостающие маркеры. Такой вариант я не пробовал, но думаю, что, в сравнении с моим алгоритмом, у него будут свои преимущества и недостатки.

Возможности извлечь из данных более точную и подробную информацию не вижу. Но тогда выходит, что импутация не даёт возможности построить более хорошее дерево, или вообще как-то улучшить предикцию для нашего 67-маркерного гаплотипа, раз мы вынуждены отталкиваться от уже существующего древа.
Если же действовать без построения дерева, а по общей частотности, то это должно давать более плохую предикцию, по-моему.
100% - перед текущим алгоритмом, я пробовал частотный/усредняющий/медианный и пр. примитивные методы: вреда от них больше, чем пользы :D

Просто, допустим, мы натравили нейросеть на массив значений стр-маркеров. Чтобы делать правильные предикции, она должна находить "сцепки" - "с таким-то значением маркера А обычно идут такие-то значения маркера Б". Чем больше сцепок найдётся, тем лучше результат. Но нахождение всех сцепок ведь и будет аналогично построению правильного дерева. Если, конечно, мы считаем разные маркеры мутирующими независимо. Если же между ними реально существует какая-то связь, то тогда нейросеть может быть лучше дерева.
Вот это очень похоже на то, что использовал я. Условно, это можно было бы назвать микро-импутацией, т.е. мы берем 67 маркеров и пытаемся предсказать наиболее предсказуемый 68-й маркер с помощью какого-либо алгоритма (можно использовать как те же методы, что и в макро-импутации - поиск по древу/N-ближайших соседей, так и методы, ищущие нелинейные связи между маркерами, т.е. названные Вами "сцепки" - я пошел как раз по второму пути, хотя и 1-й, с применением ближайших соседей, работает отлично). Когда 68-й маркер предсказан, мы берем 68 маркеров и пытаемся предсказать следующий по предсказуемости 69-й маркер и т.д. до заполнения всего 111-маркерного гаплотипа.
Разве что по нейросетям с Вами не согласен: нейросети это про извлечение признаков, а не про их интерпретацию - в интерпретации рулят деревья (леса, бэггинг, бустинг).


Оффлайн AleksG

  • Maternal Y-DNA: R-L365->YP940>R-Y110693
  • Сообщений: 876
  • Страна: 00
  • Рейтинг +389/-4
  • Y-ДНК: Q-PH2513
  • мтДНК: U5a1a1a
 Правильно понимаю что два любых совпадающих Y-67 в итоге будут предиктированы как совпадающие по Y-111?

Оффлайн Daemon2017Автор темы

  • Сообщений: 2159
  • Страна: ru
  • Рейтинг +1045/-18
  • Y-ДНК: R1a-Y35174
  • мтДНК: V7-a2a2a2b*
Правильно понимаю что два любых совпадающих Y-67 в итоге будут предиктированы как совпадающие по Y-111?

Да, всё так: предсказания всегда будут одинаковыми.

Оффлайн AleksG

  • Maternal Y-DNA: R-L365->YP940>R-Y110693
  • Сообщений: 876
  • Страна: 00
  • Рейтинг +389/-4
  • Y-ДНК: Q-PH2513
  • мтДНК: U5a1a1a
Правильно понимаю что два любых совпадающих Y-67 в итоге будут предиктированы как совпадающие по Y-111?

Да, всё так: предсказания всегда будут одинаковыми.

Тогда, развивая мысль, все кто у меня на Y-67 имеют дистанцию, скажем в 1-4 шага - на Y-111 тоже останутся на пропорциональном количестве шагов ?
Но на практике так не бывает - всех разносит вплоть до 10 и дальше (но дальше чем 10 на 111 уже не показывает даже).
Вот у меня есть 310 совпаденцев на 67 и 89 на 111. Покажу наиболее близкие, чтоб было понятно насколько это все непредсказуемо:


Оффлайн Valery

  • Сообщений: 10107
  • Страна: 00
  • Рейтинг +1380/-7
  • Ultimate Matriarchy
берем весь доступный гаплотип и, с помощью поиска по древу или N-ближайших соседей, находим его филогенетическую родню, после чего берем от нее недостающие маркеры.

Если место на дереве известно точно, то это стандартная процедура, называется "малой задачей филогенетики", или просто labelling. Недостающие признаки помечаются как missing states (на письме "?") и запускается лейблинг. Его проводят по-разному в зависимости от метода, есть парсимонный и макс. правдоподобный лейблинг. В общем случае число возможных оптимальных лейблингов дерева экспоненциально зависит и от числа признаков (как бы необходимое зло, тк признаки независимы), и от числа таксонов (а вот это уже печально).

Парсимонный лейблинг имеет долгую историю, для метрики самого общего вида алгоритм описал Санкофф еще в 1971г. Для STR обычно используется метрика Вагнера ( тупо: dist(14,17)=3 ), для нее есть чуть более быстрые способы лейблинга и несколько упрощенные способы как "найти все оптимальные лейблы". Набор таких оптимальных значений для узла (внутреннего либо помеченного ? исходного) всегда является промежутком, есть специальный термин - интервал Фарриса. Эти алгоритмы сложились еще в 1980е гг, до эпохи массового типирования STR. Их отточили на признаках более классической природы, вроде длины хвоста  ;D

YFull использует для предикции аллелей STR собственную версию парсимонного лейблинга (и, как мне помнится по описанию Вадима), аналог интервалов Фарриса.

Оффлайн Valery

  • Сообщений: 10107
  • Страна: 00
  • Рейтинг +1380/-7
  • Ultimate Matriarchy
Если наш гаплотип попадает сразу в несколько узлов, получаем неоднозначный результат (гомоплазия)

и без гомоплазии, в общем случае задача оптимизации лейблов на фиксированном дереве уже для одного признака имеет экспоненциально зависящее от числа таксонов число решений. Даже для простейшей из метрик - сниповой (метрика Фитча, выражаясь на фило-фене).

Гомоплазия никак не может влиять на реконструкцию аллелей, когда дерево уже выбрано, тк лейблинг признака не зависит от лейблинга других признаков. Гомоплазия влияет именно на выбор топологии дерева, а лейблинги потом можно делать по любому дереву в любом желаемом числе вариантов и любом удалении от оптимума. Сначала - большая задача филогенетики (найти топологию), затем - малая (отлейблить дерево). При поиске оптимальной топологии постоянно используется лейблинг, это для пользователя программы задачи большая и малая как бы разделены: сначала первая и затем вторая. Внутри же большая задача использует малую миллионы раз. Собственно, в парсимонии оптимальная стоимость топологии = минимальная стоимость лейблинга данной топологии. Аналогично в лайклихуде: правдоподобие топологии = максимуму правдоподобия возможных лайклихуд лейблингов.

« Последнее редактирование: 21 Декабрь 2022, 01:34:28 от Valery »

Оффлайн Valery

  • Сообщений: 10107
  • Страна: 00
  • Рейтинг +1380/-7
  • Ultimate Matriarchy
Лейблинг - наиболее базовый кирпичик вычислительной филогенетики. Есть просто лейблинг, как описано выше. Есть бранч-лейблинг: как пометить за один проход все внутренние линки дерева, чтобы выбрать куда подсадить новый таксон за минимальную цену, Есть реаррейнджмент-лейблинг - когда вы делаете элементарное возмущение дерева вроде nni, spr, tbr - как наиболее быстро посчитать стоимость модификации и найти оптимальное место где ее сделать. Есть коллапс-лейблинг - как найти все линки данной топологии, которые при любом оптимальном лейблинге будут без мутаций (это можно за 2 прохода). И еще много других более специальных лейблингов.

Задача "найти недостающие STR", как выше уже упоминал, в парсимонии решается поиском интервалов Фарриса, это можно сделать за 2 прохода по дереву. Для лайклихуда значительно сложнее, разумеется.

Лейблинги являются наиболее тяжелыми по затрачиваемой памяти и по времени вычислительными процедурами. Поскольку для разных признаков они независимы, то прекрасно параллелятся. Для самых тупых метрик вроде фитчевской матрицу данных вообще переиначивают, превращая ее всю в битовое поле и потом параллелят. Так делают и в парсимонии и в лайклихуде. Наиболее попсовые программы используют CUDA, а также x86-малтимидию. То есть если вы живете на arm и ppc, все будет несколько дольше чем на x86ой попсе (я, как старый рисковод, всегда на это натыкался).

Оффлайн Valery

  • Сообщений: 10107
  • Страна: 00
  • Рейтинг +1380/-7
  • Ultimate Matriarchy
Наиболее попсовые программы используют CUDA, а также x86-малтимидию. То есть если вы живете на arm и ppc, все будет несколько дольше чем на x86ой попсе (я, как старый рисковод, всегда на это натыкался).

офф
в добрые незабвенные 90е все было наоборот: машина sun sparc прекрасно делала битовые операции, а x86 сосал, тк не было команды popcount, на которой завязан быстрый лейблинг в метрике фитча. Потом ху86 обзавелся симдом и начал быстро и сердито вытеснять риск-машины из областей куда раньше даже не совался  ;D

Оффлайн Farroukh

  • Maternal Y-DNA: R1b-BY124371
  • ...
  • Сообщений: 17099
  • Страна: az
  • Рейтинг +5911/-17
  • Paternal Mt-DNA: M9a1b1
    • Azerbaijan DNA Project
  • Y-ДНК: E-Y37518
  • мтДНК: F2f1
Daemon2017 - плюсы, респект и рахмат за креативность в этой области!
Заклёвывать критикой - это и возрастное, и общесоветское, а тут ещё они и совместились в одной точке :)

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

 

© 2007 Молекулярная Генеалогия (МолГен)

Внимание! Все сообщения отражают только мнения их авторов.
Все права на материалы принадлежат их авторам (владельцам) и сетевым изданиям, с которых они взяты.