Минимальная эволюция - Minimum evolution - Wikipedia

Минимальная эволюция это дистанционный метод занят в филогенетика моделирование. Он разделяет с максимальная экономия аспект поиска филогении с наименьшей суммой длин ветвей.[1][2]

Теоретические основы критерия минимальной эволюции (МЭ) заложены в основополагающих работах Кидда и Сгарамелла-Зонта.[3] и Ржецкий и Ней.[4] В этих рамках молекулярные последовательности из таксонов заменены набором мер их несходства (т.е. так называемыми «эволюционными расстояниями»), и фундаментальный результат гласит, что если бы такие расстояния были несмещенными оценками истинные эволюционные расстояния от таксонов (то есть расстояния, которые можно было бы получить, если бы были доступны все молекулярные данные по таксонам), то истинная филогения таксонов будет иметь ожидаемую длину короче, чем любой другой возможный филогенет Т, совместимый с этими расстояниями.

Отношения и различия с максимальной экономией

Здесь стоит отметить тонкое различие между критерием максимальной экономии и критерием ME: в то время как максимальная экономия основана на абдуктивной эвристике, т. Е. На правдоподобности простейшей эволюционной гипотезы таксонов по отношению к более сложным из них, Критерий ME основан на предположениях Кидда и Сгарамелла-Зонта, которые 22 года спустя подтвердили Ржецкий и Неи. Эти математические результаты освобождают критерий ME от бритва Оккама принцип и дать ему прочную теоретическую и количественную основу.

Статистическая согласованность

Известно, что критерий ME является статистически непротиворечивым всякий раз, когда длины ветвей оцениваются с помощью Обычные наименьшие квадраты (OLS) или через линейное программирование.[5] [6][7] Однако, как отмечается в статье Ржецкого и Нея,[8] Филогения, имеющая минимальную длину в рамках модели оценки длины ветви OLS, может быть охарактеризована в некоторых обстоятельствах отрицательными длинами ветвей, которые, к сожалению, не имеют биологического значения.

Чтобы устранить этот недостаток, Пауплин[9] предложил заменить OLS новой конкретной моделью оценки длины ветви, известной как Сбалансированная минимальная эволюция (BME). Ричард Деспер и Оливье Гаскуэль[10] показали, что модель оценки длины ветви BME обеспечивает общую статистическую согласованность филогении минимальной длины, а также неотрицательность ее длин ветвей, если оцененные эволюционные расстояния от таксонов удовлетворяют неравенству треугольника.

Ле Си Винь и Арндт фон Хезелер[11] с помощью массовых и систематических имитационных экспериментов показали, что точность критерия МЭ в рамках модели оценки длины ветви BME является наивысшей в мире. дистанционные методы и не уступает альтернативным критериям, основанным, например, на максимальном правдоподобии или байесовском выводе. Более того, как показал Даниэле Катандзаро, Мартин Фрон и Раффаэле Пезенти,[12] Филогенез минимальной длины в рамках модели оценки длины ветви BME можно интерпретировать как (оптимальное по Парето) дерево консенсуса между параллельными процессами минимальной энтропии, кодируемыми лесом из n филогений, основанных на n проанализированных таксонах. Предполагается, что эту интерпретацию, основанную на теории информации, разделяют все дистанционные методы в филогенетике.

Алгоритмические аспекты

Поиск филогении кратчайшей длины обычно осуществляется с помощью точных подходов, таких как описанные в [13] [14] [15] [16] [17] [18] [19] а также эвристика такой как присоединение к соседу алгоритм,[20] FASTME, или другой метаэвристика [21]

Смотрите также

Рекомендации

  1. ^ Катандзаро, Даниэле (2010). Оценка филогении по молекулярным данным, в Математические подходы к анализу последовательности полимеров и смежные проблемы. Спрингер, Нью-Йорк.
  2. ^ Катандзаро Д. (2009). «Задача минимальной эволюции: обзор и классификация». Сети. 53 (2): 112–125. Дои:10.1002 / нетто.20280.
  3. ^ Кидд К.К., Сгарамелла-Зонта Л.А. (1971). «Филогенетический анализ: понятия и методы». Американский журнал генетики человека. 23: 235–252.
  4. ^ Ржецкий А, Ней М (1993). «Теоретические основы минимального эволюционного метода филогенетического вывода». Молекулярная биология и эволюция. 10: 21073–1095.
  5. ^ Ржецкий А, Ней М (1993). «Теоретические основы минимального эволюционного метода филогенетического вывода». Молекулярная биология и эволюция. 10: 21073–1095.
  6. ^ Деспер Р., Гаскуэль О. (2005). Основанный на минимальном эволюционном расстоянии подход к филогенетическому выводу в математике эволюции и филогении. Издательство Оксфордского университета, Нью-Йорк.
  7. ^ Катандзаро Д., Арингиери Р., Ди Сумма М., Песенти Р. (2015). «Алгоритм перехода цены и сокращения для задачи минимальной эволюции». Европейский журнал операционных исследований. 244 (3): 753–765. Дои:10.1016 / j.ejor.2015.02.019.
  8. ^ Ржецкий А, Ней М (1993). «Теоретические основы минимального эволюционного метода филогенетического вывода». Молекулярная биология и эволюция. 10: 21073–1095.
  9. ^ Пауплин Y (2000). «Прямой расчет длины дерева с помощью матрицы расстояний». Журнал молекулярной эволюции. 51 (1): 41–47. Bibcode:2000JMolE..51 ... 41P. Дои:10.1007 / s002390010065. PMID  10903371. S2CID  8619412.
  10. ^ Деспер Р., Гаскуэль О. (март 2004 г.). «Теоретические основы сбалансированного минимального эволюционного метода филогенетического вывода и его связь с подгонкой дерева методом взвешенных наименьших квадратов». Молекулярная биология и эволюция. 21 (3): 587–98. Дои:10.1093 / молбев / мш049. PMID  14694080.
  11. ^ Вин LS, фон Хезелер А (2005). «Кратчайшая триплетная кластеризация: реконструкция крупных филогений с использованием репрезентативных наборов». BMC Bioinformatics. 6: 1–14. Дои:10.1186/1471-2105-6-1. ЧВК  545949. PMID  15631638.
  12. ^ Катандзаро Д., Фрон М., Песенти Р. (2020). "Взгляд теории информации на сбалансированную проблему минимальной эволюции". Письма об исследованиях операций. 48 (3): 362–367. Дои:10.1016 / j.orl.2020.04.010.
  13. ^ Катандзаро Д., Лаббе М., Песенти Р., Салазар-Гонсалес Дж. Дж. (2009). «Математические модели для реконструкции филогенетических деревьев по критерию минимальной эволюции». Сети. 53 (2): 126–140. Дои:10.1002 / нетто.20281.
  14. ^ Аринхиери Р., Катандзаро Д., Ди Сумма М. (2011). «Оптимальные решения задачи сбалансированной минимальной эволюции». Компьютеры и исследования операций. 38 (12): 1845–1854. Дои:10.1016 / j.cor.2011.02.020.
  15. ^ Катандзаро Д., Лаббе М., Песенти Р., Салазар-Гонсалес Дж. Дж. (2012). «Задача сбалансированной минимальной эволюции». ИНФОРМС Журнал по вычислительной технике. 24 (2): 276–294. Дои:10.1287 / ijoc.1110.0455.
  16. ^ Катандзаро Д., Лаббе М., Песенти Р. (2013). «Задача сбалансированной минимальной эволюции при неопределенных данных». Дискретная прикладная математика. 161 (13–14): 1789–1804. Дои:10.1016 / j.dam.2013.03.012.
  17. ^ Катандзаро Д., Арингиери Р., Ди Сумма М., Песенти Р. (2015). «Алгоритм ветвления цены и сокращения для задачи минимальной эволюции». Европейский журнал операционных исследований. 244 (3): 753–765. Дои:10.1016 / j.ejor.2015.02.019.
  18. ^ Катандзаро Д., Песенти Р. (2019). "Перечисление вершин сбалансированного многогранника минимальной эволюции". Компьютеры и исследования операций. 109: 209–217. Дои:10.1016 / j.cor.2019.05.001.
  19. ^ Катандзаро Д., Песенти Р., Вулси Л. (2020). «О сбалансированном многограннике минимальной эволюции». Дискретная оптимизация. 36: 100570. Дои:10.1016 / j.disopt.2020.100570.
  20. ^ Гаскуэл О., Сталь М (2006). "Соседство обнаружено". Молекулярная биология и эволюция. 23 (11): 1997–2000. Дои:10.1093 / molbev / msl072. PMID  16877499.
  21. ^ Катандзаро Д., Песенти Р., Милинкович М.С. (2007). «Алгоритм оптимизации муравьиной колонии для филогенетической оценки по принципу минимальной эволюции». BMC Эволюционная биология. 7: 228. Дои:10.1186/1471-2148-7-228. ЧВК  2211314. PMID  18005416.

дальнейшее чтение

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