Байесовский подход в филогенетике позволяет получить наиболее вероятное филогенетическое дерево при заданных исходных данных, последовательностях ДНК или белков рассматриваемых организмов и эволюционной модели замен[1]. Для снижения вычислительной сложности алгоритма расчёт апостериорной вероятности реализуется различными алгоритмами, использующими метод Монте-Карло для марковских цепей[2]. Главными преимуществами байесовского подхода по сравнению с методами максимального правдоподобия и максимальной экономии является вычислительная эффективность, способность работать со сложными моделями эволюции, а также то, что, в отличие от методов, указывающих на единственное наилучшее по заданному критерию дерево, он позволяет выбрать несколько вариантов филогенетического дерева с наибольшим значением апостериорной вероятности[3].
Байесовский подход является развитием вероятностного метода, разработанного английским математиком и священником Томасом Байесом на основе теоремы Байеса. Этот метод был опубликован в 1763 году[4], через два года после его смерти. Позднее современную формулировку теоремы вывел Пьер-Симон Лаплас[1] .
В 1953 году Николас Метрополис ввёл методы Монте-Карло для марковских цепей (MCMC, Markov chain Monte Carlo)[5]. Преимущества в скорости вычислений и возможность интеграции с методами MCMC позволили байесовскому подходу стать одним из самых популярных методов статистического вывода. Байесовский подход имеет множество применений в молекулярной филогенетике и систематике. По сравнению с другими методами построения филогенетических деревьев (метод максимальной экономии, метод максимального правдоподобия), он позволяет учитывать филогенетическую неопределенность, использовать априорную информацию и сложные модели эволюции, для которых традиционные методы имеют вычислительные ограничения.
Применение байесовского подхода в филогенетике состоит в следующем. Всё множество допустимых филогенетических деревьев описывается дискретными параметрами (топология деревьев) и непрерывными параметрами (длины ветвей деревьев и параметры эволюционной модели замен). Чтобы вычислить значение апостериорной плотности распределения вероятностей для дерева c топологией и параметрами , при заданных исходных данных , применяется формула Байеса , где — условная плотность распределения вероятностей исходных данных . Знаменатель в этой формуле вычисляется по формуле полной вероятности в виде суммы по интегралов от произведения по , где — априорная плотность распределения для деревьев[6]. Явные аналитическое расчеты по этой формуле не всегда возможны, а численные — требуют большого количества вычислений при поиске максимума функции по . Применение метода статистических испытаний (который также называется методом Монте-Карло) на цепях Маркова позволяет получить приближенные значения апостериорных вероятностей и уменьшить вычислительную сложность алгоритма поиска наиболее вероятного дерева по критерию максимума апостериорной вероятности.
В методах MCMC апостериорная плотность вычисляется за счет имитации работы цепи Маркова, состояниями которой являются филогенетические деревья[2]. Расчет апостериорной плотности выполняется как частота посещения этих состояний в установившемся режиме. Наиболее вероятное дерево определяется по максимальной частоте того состояния, которое чаще всего посещается, или нескольких из них наиболее часто посещаемых. Методы MCMC можно описать двумя этапами: на первом применяется стохастический механизм для получения нового состояния цепи Маркова; на втором выполняется расчет вероятности перехода в это состояние и разыгрывается случайное событие смены состояния. Эта процедура повторяется тысячи или миллионы раз. Доля времени, в течение которого одиночное дерево посещается в процессе работы цепи Маркова, является достаточно точной аппроксимацией для его апостериорной вероятности. К числу наиболее часто применяемых алгоритмов, использующихся в методах MCMC, относятся алгоритм Метрополиса — Гастингса, алгоритм Метрополиса в сочетании с MCMC (MC³) и алгоритм LOCAL Ларгета и Симона.
Алгоритм Метрополиcа — Гастингса[7] является одним из наиболее распространенных методов MCMC и представляет собой модифицированную Гастингсом версию алгоритма Метрополиса[5]. Алгоритм Меторополиса — Гастингса строит случайную реализацию цепи Маркова, состояниями которой являются филогенетические деревья. При имитации изменения состояния на каждом шаге выполняется переход от одного дерева к другому за счет изменения топологии или параметров эволюционной модели по определённому правилу. Алгоритм состоит из следующих шагов[8]:
(под подразумевается условная вероятность или плотность распределения при заданных исходных данных );
В оригинальном алгоритме Метрополиса предполагается, что вероятности переходов от дерева к дереву и обратно равны. Если это условие не выполняется, то применяются поправки Гастингса, состоящие в следующем: вероятность перехода вычисляется по формуле , где — совместная функция распределения.
Алгоритм Метрополиса в сочетании с MCMC (Metropolis-coupled MCMC, MC³)[9], известный также как алгоритм параллельного отжига, является модифицированной версией алгоритма Метрополиса — Гастингса для марковских цепей со сложным и многомодальным распределением вероятностей состояний. Для этих случаев алгоритмы эвристического поиска деревьев критериями MP (метод максимальной экономии, maximum parsimony), ML (метод максимального правдоподобия) и ME (метод минимальной эволюции), а также МСМС могут выйти на локальный максимум, что приведёт к неверной аппроксимации апостериорной плотности распределения вероятностей. Алгоритм MC³ за счёт смешивания марковских цепей с разной температурой позволяет правильно аппроксимировать распределение апостериорных вероятностей и избегать попадания в локальные оптимумы.
Алгоритм параллельно запускает цепей, по итераций в каждой цепи с разными стационарными распределениями , , где первое распределение с целевой плотностью называется холодной цепью, а другие цепи с распределениями , называются разогретыми[10]. Плотности распределений разогретых цепей имеют вид:
Возведение плотности в степень при имеет эффект уплощения распределения по аналогии с нагреванием металла. В таком распределении легче перемещаться между пиками, разделёнными долинами, чем в первоначальном распределении. После каждой итерации алгоритм предписывает выполнить обмен состояний между двумя случайно выбранными цепями с помощью предложенного Метрополисом шага. Обмен между состояниями и происходит с вероятностью:
Эвристически, разогретые цепи будут посещать локальные пики довольно легко, и обмен состояниями между цепями позволит холодной цепи иногда перепрыгивать через долины. Если слишком мало, обмен состояниями будет редко выполняться, поэтому в алгоритме используются несколько цепей с разными температурными факторами для улучшения смешивания[6].
Для получения стационарного распределения вероятностей используются только состояния из холодной цепи, а состояния из разогретых цепей отбрасываются.
Для генерации нового состояния марковской цепи существуют различные вероятностные способы модификации деревьев, например, бисекция с последующим переприсоединением, обмен ветвей, замена на ближнее соседнее дерево. Алгоритмы LOCAL[2] и GLOBAL[12] предлагают другой способ построения нового дерева по текущему за счёт изменения топологии и длин ветвей. Это приводит к значительному сокращению вычислений для больших деревьев по сравнению с алгоритмами бутстрэпа для методов максимального правдоподобия и максимальной экономии.
Общая идея заключается в том, что дерево представляется в виде следующих параметров: топология дерева и длина его ветвей, а также параметры модели замен. При изменении состояний марковской цепи выполняются последовательные шаги, в которых отдельно либо меняется топология дерева и длина его ветвей, либо меняются только параметры модели замен. Решение о переходе к новому дереву в качестве текущего состояния цепи Маркова принимается так же, как в алгоритме Метрополиса — Гастингса, но значение пороговой вероятности вычисляется с использованием параметров модифицированного дерева.
В алгоритме GLOBAL[12], представленном Мау, Ньютоном и Ларгетом в 1999 году, все длины ветвей дерева изменяются на небольшую величину в каждом цикле. Алгоритм Ларгета и Симона LOCAL[2] предполагает модификацию дерева в небольшой окрестности случайно выбранной внутренней ветви дерева.
Построение нового дерева в алгоритме LOCAL при модификации топологии и длин ветвей выполняется по следующему правилу: равновероятно выбирается произвольное внутреннее ребро дерева с вершинами и . Вследствие того, что филогенетическое дерево должно быть бинарным, а ребро внутреннее, у каждой из вершин обязательно есть две смежные. Смежные вершины для произвольным образом обозначаются буквами и , а смежные вершины для — буквами и . Далее для вершин и равновероятно выбирается по одной смежной, например, и , и рассматривается путь между вершинами и , состоящий из трёх рёбер. Длины этих рёбер модифицируются пропорционально путём умножения на случайное число по правилу , где — старая длина пути, — новая длина пути, — это равномерно распредёленная случайная величина на отрезке , а — это положительный настраиваемый параметр. Следующий шаг модификации дерева состоит в отсоединении одной из вершин, или , выбираемых равновероятно, и присоединения её в случайно выбранной по равномерному закону точке на пути от вершины до вершины вместе с её дочерней ветвью. При такой модификации возможно изменение топологии дерева, если порядок следования вершин и вдоль пути от к изменился, иначе — топология дерева не изменяется. Поправка Гастингса равна квадрату отношения длин нового и старого пути: .
При модификации параметров модели в алгоритме рассматриваются два варианта: в первом варианте, когда один параметр ограничен набором значений , новое значение параметра вычисляется прибавлением равномерно распределённой случайной величины из интервала . Если новое значение выходит за пределы допустимого диапазона [2], то остаток отражается внутрь этого отрезка. Поправка Гастингса принимается равной 1. Второй вариант составляет случай, когда модифицируется множество параметров, сумма которых равна константе. В этом случае новое множество значений этих параметров выбирается из распределения Дирихле, центрированного по текущим значениям параметров. Поправка Гастингса вычисляется как отношение плотностей Дирихле с новыми и старыми параметрами.
MrBayes Архивная копия от 25 сентября 2018 на Wayback Machine — это бесплатная программа, осуществляющая байесовский анализ филогении. Первоначально написана Джоном Хюльсенбеком и Фредериком Ронкустом в 2001 году[16]. Когда байесовские методы приобрели популярность, многие молекулярные филогенетики стали выбирать MrBayes. Программа использует стандартный алгоритм MCMC и алгоритм Метрополиса, связанный с MCMC.
MrBayes использует МСМС для приближённого вычисления апостериорных вероятностей деревьев[5]. Пользователь может поменять предположения о модели замен, априорных вероятностей и деталей МС анализа. Также программа позволяет удалять и добавлять таксоны и символы для анализа. В программе можно использовать широкий спектр моделей замен -- от стандартной модели подстановок DNA 4х4, также называемой JC69, в которой считается, что частоты оснований равны и все замены нуклеотидов происходят с равной вероятностью[17], до наиболее общей модели GTR, в которой различаются и частоты оснований, и вероятности замен. Также программа включает несколько 20х20 моделей замен аминокислот, кодоновые и дублетные модели замены ДНК. Программа предлагает различные методы для ослабления предположения о равных скоростях замен в нуклеотидных позициях[18]. MrBayes также может выводить наследственные состояния, содержащие неопределённость филогенетического дерева и параметров модели.
MrBayes 3[19] — это полностью реогранизованная и реконструированная версия первоначальной программы MrBayes. Главное новшество заключается в возможности программы приспосабливаться к неоднородности наборов данных. Такая структура позволяет пользователю смешивать модели и получать преимущество эффективности байесовского MCMC анализа, если он имеет дело с разными типами данных (например, белки, нуклеотиды, морфологические данные). По умолчанию программа использует алгоритм МСМС Метрополиса.
MrBayes 3.2 — это новая версия MrBayes, выпущенная в 2012 году[20]. Новая версия позволяет пользователю запускать несколько анализов параллельно. Также она обеспечивает более быстрое вычисление вероятностей и даёт возможность использования ресурсов графического процессора для выполнения этих вычислений. Версия 3.2 предоставляет больше опций для выходных данных, совместимых с программой FigTree и другими программами для просмотра деревьев.
Название программы | Описание | Метод | Авторы | Ссылка на сайт |
---|---|---|---|---|
Armadillo Workflow Platform | Программа, предназначенная для филогенетического и общего биоинформатического анализа | Вывод филогенетических деревьев с использованием методов ML, MP, байесовскийого подхода и др. | E. Lord, M. Leclercq, A. Boc, A.B. Diallo, V. Makarenkov[21] | https://web.archive.org/web/20161024081942/http://www.bioinfo.uqam.ca/armadillo/. |
Bali-Phy | Одновременное получение выравнивания и дерева на основе байесовскийого похода | Байесовский вывод выравниваний и филогенетических деревьев | M.A. Suchard, B. D. Redelings[22] | http://www.bali-phy.org Архивная копия от 22 марта 2021 на Wayback Machine |
BATWING | Вывод деревьев методом Байеса с созданием внутренних узлов | Байесовский анализ, демографическая история, метод расщепления популяций | I. J. Wilson, D. Weale, D.Balding[23] | http://heidi.chnebu.ch/doku.php?id=batwing Архивная копия от 5 мая 2016 на Wayback Machine |
Bayes Phylogenies | Вывод деревьев методом Байеса с использованием методов Монте-Карло для марковских цепей и Метрополиса в сочетании с MCMC | Байесовский анализ, множественные, смешанные модели (с автоматическим разбиением) | M. Pagel, A. Meade[24] | http://www.evolution.rdg.ac.uk/BayesPhy.html Архивная копия от 19 февраля 2020 на Wayback Machine |
PhyloBayes / PhyloBayes MPI | MCMC семплер для филогенетических реконструкций. | MCMC, вероятностная модель CAT, учитывающая сайт-специфичные нуклеотиды или аминокислоты | N. Lartillot, N. Rodrigue, D. Stubbs, J. Richer[25] | https://web.archive.org/web/20181218053945/http://www.phylobayes.org/ |
BEAST | Анализ молекулярных последовательностей с помощью MCMC (Bayesian Evolutionary Analysis Sampling Trees) | Байесовский анализ, релаксированные молекулярные часы, демографическая история | A. J. Drummond, A. Rambaut & M. A. Suchard[26] | http://beast.bio.ed.ac.uk Архивная копия от 22 декабря 2007 на Wayback Machine |
BUCKy | Байесовское соответствие филогенетических деревьев для генов | Байесовское соответствие с использованием модифицированного жадного консенсуса для неукоренённых квартетов | C. Ané, B. Larget, D.A. Baum, S.D. Smith, A. Rokas, B. Larget, S.K. Kotha, C.N. Dewey, C. Ané[27] | http://www.stat.wisc.edu/~ane/bucky/ Архивная копия от 24 февраля 2019 на Wayback Machine |
Geneious (MrBayes plugin) | Средства для исследования геномов и протеомов | Neighbor-joining, UPGMA, плагины MrBayes, PHYML, RAxML, FastTree, GARLi, PAUP* | A. J. Drummond,M.Suchard,V.Lefort и др.[28] | http://www.geneious.com Архивная копия от 26 января 2021 на Wayback Machine |
TOPALi | Филогенетический вывод | Выбор филогенетической модели, байесовскийий анализ и оценка филогенетических деревьев методом максимального правдоподобия, определение сайтов, находящихся под позитивным отбором, анализ положения точек рекомбинации | I.Milne, D.Lindner и др.[29] | http://www.topali.org Архивная копия от 9 апреля 2021 на Wayback Machine |
Байесовский подход широко используется молекулярными филогенетиками для различных приложений: