Метод минимума эволюции (ME)

В этом методе для каждой из возможных топологий вычисляется сумма (S) оценок длин всех ветвей дерева:

где _– оценка длины i–ой ветви, получаемая как в предыдущем разделе ; Т – общее число ветвей (2m–3 для дерева без корня, где m – число последовательностей нуклеотидов, то есть число сравниваемых форм).

В методе ME, как и в НК, рассматриваются все возможные топологии и среди них выбирается топология с наименьшим значением S.

Показано, что метод ME приводит к правильной топологии при достаточно большом числе нуклеотидов или аминокислот (п) в анализируемых последовательностях и несмещенных оценках d_ij – числа замен на сайт в качестве меры расстояния.

Метод объединения соседей был предложен Сейтоу и Неем (1987). Он также основан на принципе минимума эволюции. В этом методе не рассматриваются все возможные топологии, но на каждом этапе объединения таксонов используется принцип минимума эволюции. В итоге получаем наилучшее дерево без корня.

На начальном этапе предполагается конфигурация звезды (рис. 6.6.А), т.е. формально все таксоны – соседи. Если оценить длины ветвей такого дерева и вычислить сумму длин ветвей (S₀), она наверняка будет больше, чем сумма для истинного дерева, или построенного методом NJ в конечном итоге. Но, если отделить, например, пару соседей 1 и 2 (рис. 6.6.В), то новая сумма (S₁₂) длин всех ветвей уже будет меньше, чем S₀. Поскольку заранее не известно, какие именно пары таксонов являются соседями, рассматриваются все потенциальные пары и вычисляется частная сумма длин всех ветвей (S_ij) при отделении i–гo и j–го таксона. Затем выбирается пара таксонов i, j с наименьшим значением S_ij. Найденные соседи объединяются в один кластер, и вся процедура повторяется до полного построения дерева.



где _; m – число таксонов

Если отделяем таксоны 1 и 2, то сумма длин ветвей дерева В на рис. 6.6. равна

где _{ } Аналогично для любой пары отделенных таксонов.

Вычисляют все значения S_ij и выбирают наименьшее. Отделяют соответствующую пару (i, j), определяя таким образом новый узел А, который соединяет таксоны i и j. Рис. 6.6 С соответствует этому этапу, если i=1, j=2. Длины ветвей от этого узла А до таксонов i и j вычисляют по формулам:

Затем определяют расстояние между новым узлом (А) и каждым из остальных k таксонов:

Алгоритм отделения соседей и вычислений повторяется пока все таксоны не будут объединены в одно дерево без корня. Построенное дерево и будет деревом NJ.

Рассмотрим модельный пример. Эволюционные расстояния в процентах для 6 таксонов представлены в табл. 6.5

Общая сумма расстояний T=162. Для дерева с топологией звезды получаем оценку S₀=32,4.

Вычислим S_ij, отделяя попарно все таксоны i и j. Например, для таксонов 1 и 2 (топология В на рис. 6.6): d₁₂=9, R₁=9+12+15+20+16=72, R₂=9+7+10+15+11=52,

Результаты вычислений S_ij для всех пар таксонов представлены в табл.6.5.

Находим наименьшее значение S₁₂=29,5. Следовательно, таксоны 1 и 2 являются соседями. Обозначим новый узел А их эволюционного расхождения и оценим длины ветвей до этих таксонов: b_A1=7, b_A2=2. Вычислим расстояние между новым узлом А и другими таксонами (k). Например, расстояние между узлом А и таксоном 3 равно

Также вычисляются расстояния между узлом А и остальными таксонами. Полученные расстояния представлены в табл.6.6. Теперь можно определить новые значения S_ij по расстояниям табл. 6.6. Для этого вычисляем новые значения Т, R_i и R_j.

В цикле 2 находим пару новых соседей. Это таксоны 5 и 6, так как у них минимальное значение S_ij, S₅₆=19,3 (топология С на рис. 6.6). Создаем новый узел В и вычисляем длины ветвей от узла В до таксонов 5 и 6. b_5B=6, b_6B=2.

Таблица 6.7. Реализация метода NJ. Цикл 3.

В цикле 3 (табл.6.7.) «сближаем» пару новых соседей – кластер А и таксон 3, создавая новый узел С (топология Е на рис. 7.6.), далее – таксоны 4 и В, получая узел D. Таким образом, процедура объединения соседей завершена. Теперь можно оценить длины ветвей b_4D=3, b_CD=1 и b_BD=2. Полученное дерево представлено на рис. 6.6F.

Впервые метод MP для построения деревьев по аминокислотным последовательностям применили Эк и Дайхоф (1966). Позднее был разработан более строгий алгоритм MP для нуклеотидных последовательностей. Метод максимальной парсимонии находит дерево (или деревья), которое включает наименьшее количество замен, необходимых для объяснения различий между изучаемыми таксонами. МР близок по смыслу к МЕ, но метод оценки длины ветвей в МР отличается.

В этом методе предполагается, что нуклеотидные или аминокислотные замены равновероятны. Для каждой топологии, независимо в каждом сайте, определяется «оптимальный» нуклеотид или аминокислота предкового таксона. Критерий – наименьшее суммарное (по сайтам и ветвям) число замен. Наилучшей среди всех возможных считается топология, требующая наименьшего количества замен.

Метод MP должен строить правильное (реализованное) дерево для каждого сайта, если в процессе эволюции не было обратных и параллельных замен, а также при условии достаточно большого числа нуклеотидов (n) в последовательностях. Однако на практике эти условия не всегда выполняются, и тогда метод MP может приводить к неправильной топологии. Если, кроме того, скорость нуклеотидных замен существенно различается для разных линий, то, даже если число нуклеотидов в последовательностях стремится к бесконечности, метод MP приводит к неправильной топологии.

Но метод MP имеет ряд преимуществ по сравнению с другими методами построения деревьев. Если расстояние между последовательностями невелико (d ≤ 10%), скорость замен примерно постоянна, и число рассмотренных нуклеотидов достаточно велико, то вероятность восстановления правильной топологии больше для метода MP, по сравнению с методами, основанными на расстояниях.

В методе MP сайты, содержащие одинаковый нуклеотид (или аминокислоту) для всех таксонов (постоянные сайты), не рассматриваются, а учитываются только вариабельные сайты. Но не все вариабельные сайты информативны для поиска топологии MP. Любой сайт, для которого существуют синглетоны – одиночные замены – неинформативен, потому что нуклеотидные замены в этом сайте можно объяснить одним и тем же числом замен в любых топологиях (пример приведен ниже). Такие сайты называются сайты–синглетоны. Чтобы сайт был информативен для поиска дерева максимальной парсимонии, в нем для сравниваемых последовательностей необходимы, по крайней мере, два разных типа нуклеотида, представленные, по крайней мере, дважды (пример приведен ниже). Именно такие сайты и называются информативными для парсимонии. Необходимо отметить, что сайты–синглетоны информативны для построения топологии другими методами, и даже постоянные сайты содержат филогенетическую информацию для методов расстояний и максимального правдоподобия.

Рассмотрим пример поиска дерева максимальной парсимонии для однотипных нуклеотидных последовательностей из 4 таксонов (таблица 6.8).
Таблица 6.8. Последовательности семь нуклеотидных сайтов из 4–х таксонов.

Таксоны	Сайты
	1	2	3	4	5	6	7
1	T	T	C	G	T	G	A
2	T	C	T	T	T	T	A
3	T	C	A	C	C	T	C
4	T	C	A	A	C	G	C

Для 4–х таксонов можно построить три дерева без корня (рис. 6.7 a).

Сначала необходимо идентифицировать сайты информативные для парсимонии. Если рассмотреть первый сайт, то из табл. 6.8 видно, что он не информативен поскольку все последовательности идентичны по Т – нет замен.

Сайт 2 тоже не информативен, потому что единственная мутация в ветви, ведущей к таксону 1, для любого из трех деревьев дает одинаковую топологию (это сайт – синглетон). В сайте 3 существуют три различных нуклеотида (рис.6.7.b), но он тоже не информативен: для построения любого из трех возможных деревьев необходимы минимум 2 замены (обозначены ) . То же можно сказать и о сайте 4, только там необходимы минимум 3 замены. Сайт 5 – информативный (рис 6.7с). Он содержит два разных типа нуклеотида, представленные дважды. Для этого сайта дерево А требует только одной замены между двумя внутренними узлами дерева, тогда как деревья В и С требуют по две замены. Сайт 6 тоже информативен, поскольку для него дерево С требует только одну замену, а деревья А и В – по две (рис. 7.7d). Информативным является и сайт 7. Для этого сайта дерево А требует одну замену, а деревья В и С – по две замены (рис. 6.7е).

С

С

T

С

Если число таксонов (m) невелико (скажем, т < 10), еще возможно вычислить длины деревьев для всех топологий и найти дерево MP. Этот тип поиска дерева MP называется полный перебор (exhaustive search). Поскольку число топологий быстро возрастает с ростом т (табл. 6.1), то для больших т рассмотреть все топологии почти невозможно. Поэтому, величины L можно вычислить только для нескольких вероятных топологий. Этот тип поиска называется поиск специфичных деревьев (specific–tree search).

Если поиск специфичных деревьев также невозможен, существует два метода поиска дерева MP при т > 10. Один из них – метод сцепления ветвей (branch–and–bound method). В этом методе деревья с длиной L большей, чем для уже рассмотренных деревьев, не учитываются, а дерево MP определяется среди группы деревьев предположительно меньшей длины. Но даже этот метод требует очень много машинного времени, если т ≥ 20.

В таком случае следует использовать т.н. эвристический поиск (heuristic search). Но и в этой стратегии поиска рассматривается только часть всех возможных деревьев, и нет гарантии, что будет найдено правильное дерево MP. Предложен ряд алгоритмов, повышающих вероятность найти такое дерево MP.

Очень часто метод максимальной парсимонии находит несколько деревьев с одинаковой минимальной длиной (L), то есть все они одинаково парсимоничны. В этом случае результат можно представить в виде «обобщенного» дерева. Такое обобщенное дерево называется деревом консенсуса. Чаще всего используются 2 типа деревьев консенсуса:

1. 
   Дерево абсолютного консенсуса;
   

2) Дерево консенсуса большинства.

Для построения такого дерева выбирают тот характер ветвления, который встречается у 50% и более рассматриваемых деревьев. Для деревьев А, В и С деревом 50% консенсуса большинства является дерево Е (рис. 6.8).

A

Рис. 6.8 Примеры деревьев консенсуса для одинаково парсимоночных деревьев А, В и С: D – дерево абсолютного консенсуса; Е – дерево 50%–го консенсуса большинства; F – дерево 70% консенсуса большинства

Если число обратных и параллельных замен достаточно велико, то методы МР часто приводят к неправильной топологии. В таких ситуациях можно использовать взвешенную парсимонию. То есть заменам в медленно–эволюционирующих сайтах можно придать больший вес при анализе. Например, учитывая различную скорость эволюции в разных позициях кодона, заменам в кодонах можно придать соответствующие веса: w₁ = 3, w₂ = 5, и w₃ = 1, так как скорость эволюции максимальна для сайтов в третьей позиции и минимальна во второй.

Можно ввести разные веса для разных типов замен. Например, если транзиции встречаются в два раза чаще трансверсий, можно ввести вес для трансверсий w = 2.