5.4. Построение дерева методом максимальной экономии

Одним из критических недостатков дистанционных методов построения дерева заключается в том, что, поскольку они начинаются со сведения полных данных о последовательности ДНК к набору попарных расстояний между таксонами, то они могут не использовать всю информацию об исходных последовательностях.

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

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

В качестве первого шага реализации намеченного плана понадобится найти способ вычисления оценки экономии для определенного дерева и последовательностей. Предположим, что смотрим на один участок в ДНК для каждого из таксонов и видим, например, : A,  : T,  : T,  : G,  : A.

Если представить, что они были связаны деревом, показанным на рисунке 5.18, то можно пройти обратно вверх по дереву, чтобы определить, какое основание могло быть на этом на каждой внутренней вершине, предполагая наименьшее количество возможных мутаций.

Рисунок 5.18. Вычисление оценки экономии для дерева на одном сайте.

Например, выше  и  мог быть либо A, либо T, но не C или G, и, по крайней мере, должна была произойти 1 мутация. Обозначаем эту вершину двумя возможностями {A, T}, но до сих пор имеем количество мутаций равное 1. Однако, учитывая то, что в  появляется T, на вершине, соединяющей  с  и  должно быть T; никакой дополнительной мутации не требуется, кроме той, которую уже посчитали. Теперь обозначили две внутренние вершины и по-прежнему имеем одну мутацию.

Продолжая продвигаться вверх по дереву, помещаем основание или набор возможных оснований на каждой вершине. Если под вершиной находятся два разных основания (или множества оснований, которые не пересекаются), нужно будет увеличить количество мутаций на 1 и объединить два основания (или взять объединение множеств) в один больший набор возможных оснований на более высокой вершине. Если два низших основания согласуются (или множества имеют общие элементы), то обозначаем высшую вершину этим основанием (или пересечением двух множеств). В этом случае не нужно подсчитывать дополнительную мутацию. Когда все вершины дерева помечены, конечное значение количества мутаций дает минимальное количество мутаций, необходимое для того, чтобы это дерево правильно описало эволюцию таксонов. Таким образом, дерево на рисунке 5.18 будет иметь минимальное количество мутаций, или показатель экономии, равный 3.

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

Во-вторых, показатель экономии дерева не зависит от расположения корня. Если используется одно и то же дерево, но корень перемещается, то данный метод подсчета может привести к тому, что поставим разные основания или наборы оснований в каждой из вершин. Тем не менее, можно доказать, что будет получен тот же коэффициент экономии. Таким образом, в то время как процедура подсчета требует временной вставки корня, в действительности можно говорить о пригодности некорневого дерева. Однако всегда можно добавить внешнюю вершину, как обсуждалось в предыдущих разделах, если требуется такое расположение корня.

Наконец, поскольку метод не позволяет однозначно восстановить последовательности на внутренних вершинах, то нет возможности узнать, вдоль каких ребер происходили мутации. Это означает, что не получится определить точную длину ребра, используя количество мутаций, происходящих при переходе вдоль него. Таким образом, метод максимальной экономии – это метод, который фокусируется только вокруг использования некорневых топологических деревьев для отыскания связей таксонов.

Теперь, когда получили оценку экономии дерева на рисунке 5.18, давайте рассмотрим другое дерево, на рисунке 5.19, которое может относиться к тем же 1-базовым последовательностям. Имейте в виду, дерево рисуется с корнем только для удобства. Применяя предыдущий метод для получения маркировки на внутренних вершинах, приходим к тому, что это дерево имеет оценку экономии 2; то есть необходимы только две мутации. Таким образом, дерево на рисунке 5.19 является более экономным, чем на рисунке 5.18.

Рисунок 5.19. Более экономное дерево.

Чтобы найти наиболее экономное дерево для этих таксонов, нужно было бы рассмотреть все 15 возможных топологий некорневых деревьев с 5 таксонами и вычислить минимальное количество мутаций для каждой. Вместо того, чтобы перебирать 13 оставшихся деревьев, давайте попробуем подумать о том, какие деревья, вероятно, будут иметь низкие показатели экономии. Если оценка низкая, то  и , вероятно, будут рядом друг с другом, как  и , но  может быть где угодно.

Вопросы для самопроверки:

– Для 5 таксонов нарисуйте несколько некорневых деревьев, которые топологически отличаются от изображенных на рисунке 5.19, но также имеют оценку экономии 2.

– Объясните, почему ни одно дерево, относящееся к этим 5 таксонам, не может иметь оценку экономии 1. Подсказка: если бы для дерева требовалась только одна мутация, то как выглядели бы основания на листьях?

Существует несколько деревьев (на самом деле, пять деревьев имеют оценку экономии 2), которые можно считать наиболее экономными. Когда это происходит, использование метода экономии требует отчета обо всех найденных деревьях, которые достигают минимального балла, потому что все они одинаково хороши согласно сформулированным критериям их выбора.

При работе с реальными данными последовательности, конечно, нужно подсчитать количество мутаций, необходимых для дерева, среди всех сайтов в последовательностях. Это можно сделать так же, как и раньше, просто обрабатывая каждый сайт параллельно. Пример приведём на рисунке 5.20.

Рисунок 5.20. Вычисление оценки экономии для дерева на трех участках.

Переходя вверх по дереву, начиная с 2 последовательностей таксонов, ATC и ACC в крайнем левом углу, видим, что там не нужны мутации ни в первом, ни в третьем узлах, но понадобятся мутации во втором. Таким образом, количество мутаций теперь равно 1, а вершина предка помечена, как показано на рисунке. На вершине, где соединяется ребро из третьего таксона, обнаруживаем, что первый участок нуждается в мутации, второй нет, а третий снова нуждается. Это увеличивает количество мутаций на 2, чтобы суммарно дать 3. Наконец, в корне обнаруживаем, что нужна мутация только во втором месте, для окончательной оценки экономии 4.

Хотя это нетрудно сделать вручную с небольшим количеством сайтов, когда считается много сайтов, это становится очень трудоёмкой задачей. Хуже то, что если есть взять еще немного таксонов, то количество топологий деревьев, которые необходимо учитывать, огромно. Таким образом, метод экономии на практике выполняется только с помощью компьютера. На самом деле, при большом количестве таксонов количество возможных деревьев настолько велико, что часто компьютерные программы проверяют не все, а только определенные конфигурации, чтобы выбрать наиболее экономное сочетание. Хорошее программное обеспечение, управляемое профессиональными пользователями, часто поможет найти то, что, вероятно, будет самыми экономными деревьями, но в этом нет никакой гарантии. Это вызывает некоторое смущение у исследователей, публикующих деревья, найденные машинным перебором. Так как, не имея малейшего представления, насколько хороши найденные варианты, им приходится использовать то, что есть, пока фактически случайным образом не будет найдено ещё более оптимальной конфигурации.

Можно исключить некоторые варианты из перебора при использовании метода экономии, если заметим, что не все сайты будут влиять на количество мутаций, необходимых для дерева. Очевидным случаем является то, что если все последовательности имеют одно и то же основание в определенном сайте, то всем деревьям потребуется 0 мутаций для этого сайта. Таким образом, можем исключить этот сайт из последовательностей перед применением алгоритма. Менее очевиден случай, когда в сайте все последовательности имеют одно и то же основание (например, А), за исключением не более чем одной последовательности, каждая из которых имеет другие основания (С, Т и G). В этом случае, независимо от топологии дерева, если поставим A в каждой внутренней вершине, то получим минимально возможное количество мутаций. Это означает, что такой сайт не повлияет на то, какое дерево выберем как самое экономное. Данная возможность приводит к возникновению следующего понятия.

Определение. Информативный сайт – это сайт, на котором по крайней мере два разных основания встречаются как минимум по два раза каждое среди рассматриваемых последовательностей.

Прежде чем применять алгоритм экономии, можем исключить все неинформативные сайты из последовательностей, потому что они не повлияют на выбор самого экономного дерева. Обратите внимание, что в предыдущих примерах использовались только информативные сайты.

Метод максимальной экономии не использует ни модель молекулярной эволюции Джукса-Кантора, ни какую-либо другую явную модель мутации ДНК. Вместо этого метод подразумевает неявное предположение о том, что мутации случаются редко, а лучшее объяснение истории эволюции – это то, которое требует наименьшего количества мутаций. Между исследователями, выступающими за основанные на перечисленных моделях методы реконструкции эволюционных деревьев, и теми, кто выступает за метод экономии, велись ожесточенные, а иногда и жесткие споры. Вместо того, чтобы присоединяться к философскому спору, просто отметим, что, когда есть несколько мутаций, скрывающих предыдущие мутации, то и методы дистанцирования, и методы экономии, по-видимому, на практике работают достаточно хорошо. Предположения каждого из методов могут быть подвергнуты обоснованной критике, и многое еще предстоит сделать, чтобы найти лучшие решения.

Задачи для самостоятельного решения:

5.4.1. а. Вычислите минимальное количество базовых изменений, необходимых для деревьев на рисунке 5.21.

Рисунок 5.21.  Деревья для задачи 5.4.1.

б. Дайте по крайней мере три дерева, которые связывают наиболее экономные последовательности с одним основанием, используемые в части (a). Помните: можно перечислять таксоны в другом порядке.

в. Среди деревьев, прослеживающих эволюцию только на одном участке, как в частях (а) и (б), почему всегда можно найти дерево, требующее не более трех замен, независимо от того, сколько таксонов присутствует?

5.4.2. а. Найдите оценку экономии деревьев, изображенных на рисунке 5.22, где показаны только информативные сайты в последовательностях ДНК.

б. Нарисуйте третье возможное (некорневое) топологическое дерево, относящееся к этим последовательностям, и найдите для него оценку экономии. Какое из трех деревьев является наиболее скупым?

Рисунок 5.22. Деревья для задачи 5.4.2.

5.4.3. Рассмотрим следующие последовательности из четырех таксонов.

               :         AATCG CTGCT CGACC

               :         AAATG CTACT GGACC

               :         AAACG TTACT GGAGC

               :         AATCG TGGCT CGATC

а. Какие сайты являются информативными?

б. Используйте информативные сайты, чтобы определить наиболее скупое некорневое дерево, относящееся к этим последовательностям.

в. Если известно, что  является внешней группой, используйте свой ответ на часть (б), чтобы создать корневое дерево, относящееся к ,  и .

5.4.4. Хотя неинформативные сайты не влияют на то, какое дерево считается наиболее экономным, они влияют на показатель экономии. Объясните, почему, если  и  являются скупыми оценками для дерева, использующего все сайты и использующего только информативные сайты соответственно, то , где, для , за  обозначаем количество сайтов со всеми таксонами в согласии, за исключением  таксонов, которые все различны. Примечание: Принимая во внимание, что  и  могут быть различаться для разной топологии, значение  не зависит от топологии.

5.4.5. Для первого дерева на рисунке 5.23 рассчитайте минимальное количество требуемых изменений базы, разметив внутренние вершины по алгоритму из предыдущего раздела. Затем покажите, что второе дерево требует точно такого же количества изменений основания, даже если это не согласуется с тем, как обозначили внутренние вершины на первом дереве. Основной вывод, к которому нужно прийти после решения этой задачи заключается в том, что алгоритм, который используется для подсчета минимального количества изменений базы, необходимых для дерева, не обязательно покажет все способы, которыми можно достигнуть минимума.

Рисунок 5.23.  Деревья для задачи 5.4.5.

5.4.6. Если приведены последовательности для 3 терминальных таксонов, то информативных сайтов быть не может. Объясните, почему это так, и почему это не имеет значения.

5.4.7. Основания на определенном участке в выровненных последовательностях из разных таксонов образуют закономерность. Например, при сравнении  последовательностей на участке шаблонная запись (ATTGA) означает, что A появляется на этом участке в последовательности первого таксона, T во второй, T в третьей, G в четвертой и A в пятой.

а. Объясните, почему при сравнении последовательностей для  таксонов может появиться  возможных шаблона.

б. Некоторые шаблоны неинформативны. Простыми примерами являются четыре паттерна, показывающие одно и то же основание во всех последовательностях. Объясните, почему существуют  неинформативных паттернов, все последовательности которых совпадают, кроме одной.

в. Сколько всего существует неинформативных шаблонов, в которых 2 основания появляются один раз, а все остальные совпадают?

г. Сколько существует неинформативных шаблонов, в которых 3 основания появляется один раз, а все остальные согласованы?

д. Объедините свои ответы, чтобы рассчитать количество информативных шаблонов для  таксонов.  Являются ли большинство шаблонов информативными для больших ?

5.4.8. Компьютерная программа, вычисляющая оценки экономии, может работать следующим образом: сначала сравните последовательности и подсчитайте количество сайтов  для каждого появляющегося информативного шаблона. Затем для данного дерева вычислите оценки экономии  каждого из этих шаблонов. Наконец, используйте эту информацию для вычисления оценки экономии дерева, используя все последовательности. Какая формула необходима для выполнения заключительного шага? Другими словами, выразите оценку экономии дерева через  и .

5.4.9. Показатели экономичности можно рассчитать еще эффективнее, используя тот факт, что несколько разных шаблонов всегда дают одинаковую оценку. Например, при сопоставлении 4 таксонов шаблоны (ATTA) и (CAAC) будут иметь одинаковую оценку.

а. Используя это наблюдение для 4 таксонов определите, сколько различных информативных таблиц должно быть рассмотрено, чтобы получить оценку экономии для всех возможных комбинаций?

б. Повторите часть (а) для 5 таксонов.

5.4.10. Используйте метод максимальной экономии для построения некорневого дерева для моделируемых последовательностей a1, a2, a3 и a4 в файле данных seqdata.mat. Сначала поместите последовательности в строки массива командой a=[a1;a2;a3;a4]. Затем найдите информативные сайты самостоятельно запрограммированной функцией infosites=informative(a). Наконец, извлеките информативные сайты с помощью команды ainfo=a(:,infosites).

а. Каков процент информативных сайтов?

б. Сколько различных деревьев следует проанализировать, чтобы найти самое экономное, относящееся к четырем таксонам?

в. Бывает слишком сложно использовать все информативные сайты для ручного расчета. Если это так, то используйте хотя бы первые 10 информативных сайтов, чтобы выбрать самое экономное дерево.

г. Согласуется ли найденное дерево топологически с тем, которое получается методом UPGMA и/или методом присоединения соседей с использованием расстояния Джукса-Кантора?

5.4.11. В этой задаче попытайтесь использовать метод максимальной экономии для построения некорневого дерева для ранее смоделированных последовательностей d1, d2, d3, d4, d5 и d6 в файле данных seqdata.mat. Начните с поиска информативных сайтов, как в предыдущей задаче.

а. Каков процент информативных сайтов?

б. Вычислите количество некорневых деревьев, которые необходимо изучить, если рассматривать все комбинации.

в. Используйте метод присоединения соседей, с логарифмическим расстоянием, вычисляемым из полных последовательностей, чтобы получить дерево, которое является хорошей отправной точкой для поиска наиболее экономных. Рассчитайте его оценку экономии, используя только первые 10 информативных сайтов.

г. Опять же, используя только первые 10 информативных сайтов, найдите по крайней мере 4 других дерева, которые похожи на одно из части (в). Можно ли найти более экономные?

д. Насколько уверены в том, что самое экономное дерево, которое нашли, действительно является самым экономным из всех возможных комбинаций? Для какого процента возможных деревьев вычислили оценки экономии? Какой процент информативных сайтов использовали?