stringtranslate.com

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

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

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

Связь и сравнение с другими методами

Максимальная бережливость

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

В 1978 году было показано, что критерий максимальной экономии, использующий расстояние Хэмминга для определения длины ветвей, является статистически несостоятельным. Это привело к интересу к статистически состоятельным альтернативам, таким как МЭ. [5]

Присоединение соседа

Neighbor joining можно рассматривать как жадную эвристику для критерия сбалансированной минимальной эволюции (BME). Алгоритм NJ Сайто и Нея 1987 года намного предшествует критерию BME 2000 года. В течение двух десятилетий исследователи использовали NJ без прочной теоретической основы того, почему он работает. [6]

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

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

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

Le Sy Vinh и Arndt von Haeseler [11] показали с помощью масштабных и систематических экспериментов по моделированию, что точность критерия ME в модели оценки длины ветвей BME является самой высокой среди методов расстояния и не уступает таковым альтернативных критериев, основанных, например, на максимальном правдоподобии или байесовском выводе. Более того, как показали Daniele Catanzaro, Martin Frohn и Raffaele Pesenti [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). По сравнению с NJ, он примерно такой же быстрый и более точный. [20] Также использовались метаэвристики . [21]

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

Ссылки

  1. ^ Катандзаро, Даниэле (2010). Оценка филогений по молекулярным данным, в Математические подходы к анализу полимерной последовательности и смежные проблемы . Springer, Нью-Йорк.
  2. ^ Catanzaro D (2009). «Проблема минимальной эволюции: обзор и классификация». Networks . 53 (2): 112–125. doi :10.1002/net.20280. S2CID  6018514.
  3. ^ Kidd KK, Sgaramella-Zonta LA (1971). «Филогенетический анализ: концепции и методы». American Journal of Human Genetics . 23 (3): 235–252. PMC 1706731. PMID  5089842 . 
  4. ^ abcd Ржецкий А., Ней М. (1993). «Теоретические основы метода минимальной эволюции филогенетического вывода». Молекулярная биология и эволюция . 10 : 21073–1095.
  5. ^ abcde Катандзаро, Даниэле; Фрон, Мартин; Гаскуэль, Оливье; Пезенти, Раффаэле (июль 2022 г.). «Учебник по проблеме сбалансированной минимальной эволюции». Европейский журнал операционных исследований . 300 (1): 1–19. doi : 10.1016/j.ejor.2021.08.004 .
  6. ^ ab Gascuel O, Steel M (2006). «Раскрыто присоединение соседей». Mol Biol Evol . 23 (11): 1997–2000. doi : 10.1093/molbev/msl072 . PMID  16877499.
  7. ^ Desper R, Gascuel O (2005). Подход к филогенетическому выводу на основе минимального эволюционного расстояния в Mathematics of Evolution and Phylogeny . Oxford University Press, Нью-Йорк.
  8. ^ Катандзаро Д., Арингьери Р., Ди Сумма М., Песенти Р. (2015). «Алгоритм отраслевой цены и сокращения для задачи минимальной эволюции». Европейский журнал операционных исследований . 244 (3): 753–765. дои : 10.1016/j.ejor.2015.02.019. S2CID  1549028.
  9. ^ Pauplin Y (2000). «Прямой расчет длины дерева с использованием матрицы расстояний». Журнал молекулярной эволюции . 51 (1): 41–47. Bibcode : 2000JMolE..51...41P. doi : 10.1007/s002390010065. PMID  10903371. S2CID  8619412.
  10. ^ Desper R, Gascuel O (март 2004 г.). «Теоретическая основа метода сбалансированной минимальной эволюции филогенетического вывода и его связь с подгонкой дерева методом взвешенных наименьших квадратов». Молекулярная биология и эволюция . 21 (3): 587–98. doi : 10.1093/molbev/msh049 . PMID  14694080.
  11. ^ Vihn LS, von Haeseler A (2005). «Кластеризация кратчайших триплетов: реконструкция больших филогений с использованием репрезентативных наборов». BMC Bioinformatics . 6 : 1–14. doi : 10.1186/1471-2105-6-92 . PMC 1097715. PMID  15819989 . 
  12. ^ Catanzaro D, Frohn M, Pesenti R (2020). «Теория информации в перспективе сбалансированной минимальной эволюции». Operations Research Letters . 48 (3): 362–367. doi :10.1016/j.orl.2020.04.010. S2CID  218998400.
  13. ^ Catanzaro D, Labbé M, Pesenti R, Salazar-González JJ (2009). «Математические модели для реконструкции филогенетических деревьев при минимальном критерии эволюции». Networks . 53 (2): 126–140. doi :10.1002/net.20281. S2CID  17792339.
  14. ^ Катандзаро Д., Арингьери Р., Ди Сумма М., Песенти Р. (2015). «Алгоритм отраслевой цены и сокращения для задачи минимальной эволюции». Европейский журнал операционных исследований . 244 (3): 753–765. дои : 10.1016/j.ejor.2015.02.019. S2CID  1549028.
  15. ^ Aringhieri R, Catanzaro D, Di Summa M (2011). «Оптимальные решения для сбалансированной минимальной эволюционной проблемы». Computers and Operations Research . 38 (12): 1845–1854. doi :10.1016/j.cor.2011.02.020. hdl : 2318/86826 . S2CID  9514013.
  16. ^ Катандзаро Д., Лаббе М., Песенти Р., Саласар-Гонсалес Дж.Дж. (2012). «Проблема сбалансированной минимальной эволюции». ИНФОМС Журнал по вычислительной технике . 24 (2): 276–294. дои : 10.1287/ijoc.1110.0455.
  17. ^ Catanzaro D, Labbé M, Pesenti R (2013). «Проблема сбалансированной минимальной эволюции при неопределенных данных». Discrete Applied Mathematics . 161 (13–14): 1789–1804. doi : 10.1016/j.dam.2013.03.012 .
  18. ^ Catanzaro D, Pesenti R (2019). «Перечисление вершин сбалансированного минимального эволюционного многогранника». Computers and Operations Research . 109 : 209–217. doi :10.1016/j.cor.2019.05.001. S2CID  164835227.
  19. ^ Catanzaro D, Pesenti R, Wolsey L (2020). «О сбалансированном минимальном эволюционном многограннике». Дискретная оптимизация . 36 : 100570. doi : 10.1016/j.disopt.2020.100570. S2CID  213389485.
  20. ^ "ATGC: FastME" . www.atgc-montpellier.fr .
  21. ^ Catanzaro D, Pesenti R, Milinkovitch MC (2007). "Алгоритм оптимизации колонии муравьев для филогенетической оценки в соответствии с принципом минимальной эволюции". BMC Evolutionary Biology . 7 : 228. doi : 10.1186/1471-2148-7-228 . PMC 2211314. PMID  18005416 . 

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