Минимальная эволюция

Минимальная эволюция — это дистанционный метод, используемый в филогенетическом моделировании. Он с максимальной экономией разделяет аспект поиска филогении, имеющей наименьшую общую сумму длин ветвей. ^{[ 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 .
^ Jump up to: ^а ^б ^с ^д Ржецкий А, Ней М (1993). «Теоретические основы метода минимальной эволюции филогенетического вывода». Молекулярная биология и эволюция . 10 : 21073–1095.
^ Jump up to: ^а ^б ^с ^д ^и Катандзаро, Даниэле; Фрон, Мартин; Гаскуэль, Оливье; Пезенти, Рафаэле (июль 2022 г.). «Урок по задаче сбалансированной минимальной эволюции» . Европейский журнал операционных исследований . 300 (1): 1–19. дои : 10.1016/j.ejor.2021.08.004 .
^ Jump up to: ^а ^б Гаскуэль О, Стил М (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 .

[1] Катандзаро, Даниэле (2010). Оценка филогении на основе молекулярных данных, в книге «Математические подходы к анализу последовательностей полимеров и смежным проблемам» . Спрингер, Нью-Йорк.

[2] Катандзаро Д. (2009). «Задача минимальной эволюции: обзор и классификация». Сети . 53 (2): 112–125. дои : 10.1002/net.20280 . S2CID 6018514 .

[Kidd71-3] Кидд К.К., Сгарамелла-Зонта Л.А. (1971). «Филогенетический анализ: Концепции и методы» . Американский журнал генетики человека . 23 (3): 235–252. ПМК 1706731 . ПМИД 5089842 .

[Rz93-4] Jump up to: ^а ^б ^с ^д Ржецкий А, Ней М (1993). «Теоретические основы метода минимальной эволюции филогенетического вывода». Молекулярная биология и эволюция . 10 : 21073–1095.

[Catanzaro2022-5] Jump up to: ^а ^б ^с ^д ^и Катандзаро, Даниэле; Фрон, Мартин; Гаскуэль, Оливье; Пезенти, Рафаэле (июль 2022 г.). «Урок по задаче сбалансированной минимальной эволюции» . Европейский журнал операционных исследований . 300 (1): 1–19. дои : 10.1016/j.ejor.2021.08.004 .

[gascuel-6] Jump up to: ^а ^б Гаскуэль О, Стил М (2006). «Обнаружено присоединение соседей» . Мол Биол Эвол . 23 (11): 1997–2000. дои : 10.1093/molbev/msl072 . ПМИД 16877499 .

[7] Деспер Р., Гаскуэль О (2005). Подход к филогенетическому выводу в математике эволюции и филогении, основанный на минимальном эволюционном расстоянии . Издательство Оксфордского университета, Нью-Йорк.

[8] Катандзаро Д., Арингьери Р., Ди Сумма М., Песенти Р. (2015). «Алгоритм отраслевой цены и сокращения для задачи минимальной эволюции». Европейский журнал операционных исследований . 244 (3): 753–765. дои : 10.1016/j.ejor.2015.02.019 . S2CID 1549028 .

[9] Пауплин Ю. (2000). «Прямой расчет длины дерева с использованием матрицы расстояний». Журнал молекулярной эволюции . 51 (1): 41–47. Бибкод : 2000JMolE..51...41P . дои : 10.1007/s002390010065 . ПМИД 10903371 . S2CID 8619412 .

[10] Деспер Р., Гаскуэль О (март 2004 г.). «Теоретическая основа метода сбалансированной минимальной эволюции филогенетического вывода и его связь с подгонкой дерева взвешенных наименьших квадратов» . Молекулярная биология и эволюция . 21 (3): 587–98. дои : 10.1093/molbev/msh049 . ПМИД 14694080 .

[11] Вихн Л.С., фон Хэзелер А. (2005). «Кратчайшая кластеризация триплетов: реконструкция крупных филогений с использованием репрезентативных наборов» . БМК Биоинформатика . 6 : 1–14. дои : 10.1186/1471-2105-6-92 . ПМЦ 1097715 . ПМИД 15819989 .

[12] Катандзаро Д., Фрон М., Пезенти Р. (2020). «Текст теории информации на проблему сбалансированной минимальной эволюции». Письма об исследованиях операций . 48 (3): 362–367. дои : 10.1016/j.orl.2020.04.010 . S2CID 218998400 .

[13] Катанзаро Д., Лаббе М., Песенти Р., Саласар-Гонсалес Дж.Дж. (2009). «Математические модели для реконструкции филогенетических деревьев по критерию минимальной эволюции». Сети . 53 (2): 126–140. дои : 10.1002/net.20281 . S2CID 17792339 .

[14] Катандзаро Д., Арингьери Р., Ди Сумма М., Песенти Р. (2015). «Алгоритм отраслевой цены и сокращения для задачи минимальной эволюции». Европейский журнал операционных исследований . 244 (3): 753–765. дои : 10.1016/j.ejor.2015.02.019 . S2CID 1549028 .

[15] Арингьери Р., Катандзаро Д., Ди Сумма М. (2011). «Оптимальные решения задачи сбалансированной минимальной эволюции». Компьютеры и исследования операций . 38 (12): 1845–1854. дои : 10.1016/j.cor.2011.02.020 . hdl : 2318/86826 . S2CID 9514013 .

[16] Катанзаро Д., Лаббе М., Пезенти Р., Саласар-Гонсалес Дж.Дж. (2012). «Проблема сбалансированной минимальной эволюции». ИНФОРМС Журнал по вычислительной технике . 24 (2): 276–294. дои : 10.1287/ijoc.1110.0455 .

[17] Катандзаро Д., Лаббе М., Пезенти Р. (2013). «Проблема сбалансированной минимальной эволюции при неопределенных данных» . Дискретная прикладная математика . 161 (13–14): 1789–1804. дои : 10.1016/j.dam.2013.03.012 .

[18] Катандзаро Д., Песенти Р. (2019). «Перечисление вершин сбалансированного многогранника минимальной эволюции». Компьютеры и исследования операций . 109 : 209–217. дои : 10.1016/j.cor.2019.05.001 . S2CID 164835227 .

[19] Катандзаро Д., Песенти Р., Уолси Л. (2020). «О сбалансированном многограннике минимальной эволюции». Дискретная оптимизация . 36 : 100570. doi : 10.1016/j.disopt.2020.100570 . S2CID 213389485 .

[20] «АТГК: FastME» . www.atgc-montpellier.fr .

[21] Катандзаро Д., Пезенти Р., Милинкович М.С. (2007). «Алгоритм оптимизации колонии муравьев для филогенетической оценки в соответствии с принципом минимальной эволюции» . Эволюционная биология BMC . 7 : 228. дои : 10.1186/1471-2148-7-228 . ПМК 2211314 . ПМИД 18005416 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

v т и Филогенетика
Соответствующие поля	Вычислительная филогенетика Молекулярная филогенетика кладистика Таксономия Эволюционная таксономия Систематика	Портал эволюционной биологии
Основные понятия	Филогенез Кладогенез Филогенетическое дерево Кладограмма Филогенетическая сеть Аттракцион «Длинная ветка» Клэйд против Грейда Родословная Родословная призрака Население призраков
Методы вывода	Максимальная экономия Филогенетическое примирение Вероятностные методы Максимальная вероятность Байесовский вывод Дистанционно-матричные методы Присоединение к соседям УПГМА Наименьшие квадраты Трех-таксонный анализ
Текущие темы	Филокод ДНК-штрихкодирование Молекулярная филогенетика Филогенетические сравнительные методы Консерватизм филогенетической ниши Филогенетический сигнал Программное обеспечение для филогенетики Филогеномика Филогеография
Групповые черты	Примитивный Плезиоморфия Симплезиоморфия Полученный Апоморфия Синапоморфия Аутапоморфия
Типы групп	монофилия Парафилия Полифилия
Номенклатура	Филогенетическая номенклатура Коронная группа Сестринская группа Базальный Супердерево
Категория Коммонс