Минимальная эволюция
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
Минимальная эволюция — это дистанционный метод, используемый в филогенетическом моделировании. Он с максимальной экономией разделяет аспект поиска филогении, имеющей наименьшую общую сумму длин ветвей. [ 1 ] [ 2 ]
Теоретические основы критерия минимальной эволюции (ME) заложены в плодотворных работах Кидда и Сгарамеллы-Зонты (1971). [ 3 ] и Ржецкий и Ней (1993). [ 4 ] В этих рамках молекулярные последовательности таксонов заменяются набором показателей их несходства (т.е. так называемыми «эволюционными расстояниями»), и фундаментальный результат гласит, что если бы такие расстояния были несмещенными оценками истинных эволюционных расстояний от таксонов ( т. е. расстояния, которые можно было бы получить, если бы все молекулярные данные по таксонам были доступны), то истинная филогения таксонов имела бы ожидаемую длину короче, чем любая другая возможная филогения T, совместимая с этими расстояния.
Связь с другими методами и сравнение с ними
[ редактировать ]Максимальная экономия
[ редактировать ]Здесь стоит отметить тонкое различие между критерием максимальной экономии и критерием ME: в то время как максимальная экономия основана на абдуктивной эвристике, т. е. на правдоподобии простейшей эволюционной гипотезы таксонов по отношению к более сложным, Критерий ME основан на гипотезах Кидда и Сгарамеллы-Зонты, которые 22 года спустя были доказаны Ржецким и Неем. [ 4 ] Эти математические результаты освобождают критерий МЭ от принципа бритвы Оккама и придают ему прочную теоретическую и количественную основу.
критерий максимальной экономии, в котором используются длины ветвей расстояния Хэмминга В 1978 году было показано, что , статистически противоречив. Это привело к интересу к статистически последовательным альтернативам, таким как ME. [ 5 ]
Присоединение соседа
[ редактировать ]Присоединение соседей можно рассматривать как жадную эвристику для критерия сбалансированной минимальной эволюции (BME). Алгоритм Сайто и Нея, разработанный Нью-Джерси 1987 года, намного предшествовал критерию BME 2000 года. В течение двух десятилетий исследователи использовали Нью-Джерси без прочной теоретической основы того, почему он работает. [ 6 ]
Статистическая последовательность
[ редактировать ]Критерий ME, как известно, статистически непротиворечив, когда длины ветвей оцениваются с помощью метода наименьших квадратов (OLS) или с помощью линейного программирования . [ 4 ] [ 7 ] [ 8 ] Однако, как отмечается в статье Ржецкого и Нея, филогения, имеющая минимальную длину в соответствии с моделью оценки длины ветвей OLS, может при некоторых обстоятельствах характеризоваться отрицательной длиной ветвей, которая, к сожалению, не имеет биологического значения. [ 4 ]
Чтобы устранить этот недостаток, Пауплин [ 9 ] предложил заменить OLS новой конкретной моделью оценки длины ветвей, известной как сбалансированная базовая эволюция (BME). Ришар Деспер и Оливье Гаскюэль [ 10 ] показали, что модель оценки длины ветвей BME обеспечивает общую статистическую согласованность филогении минимальной длины, а также неотрицательность длин ее ветвей всякий раз, когда оцененные эволюционные расстояния от таксонов удовлетворяют неравенству треугольника.
Ле Си Винь и Арндт фон Хэзелер [ 11 ] показали с помощью массовых и систематических экспериментов по моделированию, что точность критерия ME в модели оценки длины ветки BME на сегодняшний день является самой высокой среди дистанционных методов и не уступает точности альтернативных критериев, основанных, например, на максимальном правдоподобии или байесовском методе. Вывод. Более того, как показали Даниэле Катандзаро, Мартин Фрон и Рафаэле Пезенти , [ 12 ] Филогению минимальной длины в соответствии с моделью оценки длины ветвей BME можно интерпретировать как (оптимальное по Парето) консенсусное дерево между параллельными процессами минимальной энтропии, кодируемыми лесом из n филогений, основанных на n анализируемых таксонах. Предполагается, что эта конкретная интерпретация, основанная на теории информации, разделяется всеми дистанционными методами в филогенетике.
Алгоритмические аспекты
[ редактировать ]«Задача минимальной эволюции» (MEP), в которой филогения минимальной суммированной длины выводится из набора последовательностей в соответствии с критерием ME, называется NP-трудной . [ 13 ] [ 14 ] «Проблема сбалансированной минимальной эволюции» (BMEP), в которой используется новый критерий BME, является APX-трудной . [ 5 ]
Описан ряд точных алгоритмов решения BMEP. [ 15 ] [ 16 ] [ 17 ] [ 18 ] Самый известный точный алгоритм [ 19 ] остается непрактичным для более чем дюжины таксонов даже при использовании мультипроцессинга. [ 5 ] Существует только один алгоритм аппроксимации с доказанными границами погрешности, опубликованный в 2012 году. [ 5 ]
На практике BMEP в основном реализуется посредством эвристического поиска . Базовый вышеупомянутый алгоритм объединения соседей реализует жадную версию BMEP. [ 6 ] FastME, «самое современное», [ 5 ] начинается с грубого дерева, а затем улучшается с помощью набора топологических ходов, таких как обмен ближайшими соседями (NNI). По сравнению с Нью-Джерси, он примерно такой же быстрый и точный. [ 20 ] метаэвристики . Также использовались [ 21 ]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Катандзаро, Даниэле (2010). Оценка филогении на основе молекулярных данных, в книге «Математические подходы к анализу последовательностей полимеров и смежным проблемам» . Спрингер, Нью-Йорк.
- ^ Катандзаро Д. (2009). «Задача минимальной эволюции: обзор и классификация». Сети . 53 (2): 112–125. дои : 10.1002/net.20280 . S2CID 6018514 .
- ^ Кидд К.К., Сгарамелла-Зонта Л.А. (1971). «Филогенетический анализ: Концепции и методы» . Американский журнал генетики человека . 23 (3): 235–252. ПМК 1706731 . ПМИД 5089842 .
- ^ Перейти обратно: а б с д Ржецкий А, Ней М (1993). «Теоретические основы метода минимальной эволюции филогенетического вывода». Молекулярная биология и эволюция . 10 : 21073–1095.
- ^ Перейти обратно: а б с д и Катандзаро, Даниэле; Фрон, Мартин; Гаскуэль, Оливье; Пезенти, Рафаэле (июль 2022 г.). «Учебник по проблеме сбалансированной минимальной эволюции» . Европейский журнал операционных исследований . 300 (1): 1–19. дои : 10.1016/j.ejor.2021.08.004 .
- ^ Перейти обратно: а б Гаскуэль О, Стил М (2006). «Обнаружено присоединение соседей» . Мол Биол Эвол . 23 (11): 1997–2000. дои : 10.1093/molbev/msl072 . ПМИД 16877499 .
- ^ Деспер Р., Гаскуэль О (2005). Подход к филогенетическому выводу в математике эволюции и филогении, основанный на минимальном эволюционном расстоянии . Издательство Оксфордского университета, Нью-Йорк.
- ^ Катандзаро Д., Арингьери Р., Ди Сумма М., Песенти Р. (2015). «Алгоритм отраслевой цены и сокращения для задачи минимальной эволюции». Европейский журнал операционных исследований . 244 (3): 753–765. дои : 10.1016/j.ejor.2015.02.019 . S2CID 1549028 .
- ^ Пауплин Ю. (2000). «Прямой расчет длины дерева с использованием матрицы расстояний». Журнал молекулярной эволюции . 51 (1): 41–47. Бибкод : 2000JMolE..51...41P . дои : 10.1007/s002390010065 . ПМИД 10903371 . S2CID 8619412 .
- ^ Деспер Р., Гаскуэль О (март 2004 г.). «Теоретическая основа метода сбалансированной минимальной эволюции филогенетического вывода и его связь с подгонкой дерева взвешенных наименьших квадратов» . Молекулярная биология и эволюция . 21 (3): 587–98. дои : 10.1093/molbev/msh049 . ПМИД 14694080 .
- ^ Вихн Л.С., фон Хэзелер А. (2005). «Кратчайшая кластеризация триплетов: реконструкция крупных филогений с использованием репрезентативных наборов» . БМК Биоинформатика . 6 : 1–14. дои : 10.1186/1471-2105-6-92 . ПМЦ 1097715 . ПМИД 15819989 .
- ^ Катандзаро Д., Фрон М., Пезенти Р. (2020). «Текст теории информации на проблему сбалансированной минимальной эволюции». Письма об исследованиях операций . 48 (3): 362–367. дои : 10.1016/j.orl.2020.04.010 . S2CID 218998400 .
- ^ Катанзаро Д., Лаббе М., Песенти Р., Саласар-Гонсалес Дж.Дж. (2009). «Математические модели для реконструкции филогенетических деревьев по критерию минимальной эволюции». Сети . 53 (2): 126–140. дои : 10.1002/net.20281 . S2CID 17792339 .
- ^ Катандзаро Д., Арингьери Р., Ди Сумма М., Песенти Р. (2015). «Алгоритм отраслевой цены и сокращения для задачи минимальной эволюции». Европейский журнал операционных исследований . 244 (3): 753–765. дои : 10.1016/j.ejor.2015.02.019 . S2CID 1549028 .
- ^ Арингьери Р., Катандзаро Д., Ди Сумма М. (2011). «Оптимальные решения задачи сбалансированной минимальной эволюции». Компьютеры и исследования операций . 38 (12): 1845–1854. дои : 10.1016/j.cor.2011.02.020 . hdl : 2318/86826 . S2CID 9514013 .
- ^ Катанзаро Д., Лаббе М., Песенти Р., Саласар-Гонсалес Дж.Дж. (2012). «Проблема сбалансированной минимальной эволюции». ИНФОРМС Журнал по вычислительной технике . 24 (2): 276–294. дои : 10.1287/ijoc.1110.0455 .
- ^ Катандзаро Д., Лаббе М., Пезенти Р. (2013). «Проблема сбалансированной минимальной эволюции при неопределенных данных» . Дискретная прикладная математика . 161 (13–14): 1789–1804. дои : 10.1016/j.dam.2013.03.012 .
- ^ Катандзаро Д., Песенти Р. (2019). «Перечисление вершин сбалансированного многогранника минимальной эволюции». Компьютеры и исследования операций . 109 : 209–217. дои : 10.1016/j.cor.2019.05.001 . S2CID 164835227 .
- ^ Катандзаро Д., Пезенти Р., Уолси Л. (2020). «О сбалансированном многограннике минимальной эволюции». Дискретная оптимизация . 36 : 100570. doi : 10.1016/j.disopt.2020.100570 . S2CID 213389485 .
- ^ «АТГК: FastME» . www.atgc-montpellier.fr .
- ^ Катандзаро Д., Пезенти Р., Милинкович М.С. (2007). «Алгоритм оптимизации колонии муравьев для филогенетической оценки в соответствии с принципом минимальной эволюции» . Эволюционная биология BMC . 7 : 228. дои : 10.1186/1471-2148-7-228 . ПМК 2211314 . ПМИД 18005416 .
Дальнейшее чтение
[ редактировать ]- Катандзаро Д., Пезенти Р., Уолси Л. (2020). «О сбалансированном многограннике минимальной эволюции». Дискретная оптимизация . 36 : 100570. doi : 10.1016/j.disopt.2020.100570 . S2CID 213389485 .
