Mol. Genet. Microbiol. Virusol. vol. 3, pages 3-9, 1988, Russian

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

Ограничения 13 имеют ясный биологический смысл, а ограничение 4 отвечает принципу максимальной экономии [7], утверждающему, что реальный ход эволюционного процесса осуществляется вдоль пути с наименьшим числом эволюционных событий.

Во-вторых, как недавно выяснилось, деревья максимальной экономии неустойчивы к локальным изменениям данных. Это означает, что при работе с филогениями, построенными по принципу максимальной экономии, теоретически возможна ситуация, когда, например, незначительные изменения данных об одном виде бабочек, возможно, не требующие изменения классификации Lepidoptera, повлекут за собой изменение филогении Diptera или даже более далеких таксономических групп [14].

И, наконец, в настоящее время неизвестны алгоритмы, строящие большие деревья максимальной экономии за приемлемое время. Более того, показано, что задача построения дерева максимальной экономии принадлежит к классу так называемых NPполных задач, что делает, крайне маловероятной возможность существования таких алгоритмов [13]. Поэтому применяемые на практике алгоритмы являются приближенными, т. е. строят не сами деревья максимальной экономии, а только приближения к ним, а это во многом обесценивает сам подход.

В любом случае эту задачу можно разбить на 2 последовательных независимых этапа: выбор оптимальной топологии (структуры) дерева и определение оптимальных длин ветвей. Очевидно, что определение общей структуры дерева является существенно более важной задачей по сравнению с определением конкретных значений длин ветвей дерева. Вторая задача решается эффективно, и основную трудность представляет 1й этап. Для решения этой задачи целесообразно в максимальной степени отвлечься от конкретных расстояний и сосредоточить основное внимание на выборе общей структуры дерева. Такой топологический подход был предложен W. Fitch [10]. Для описания этого метода необходимо ввести некоторые топологически определения. Графом называется множество элементов, называемых вершинами, и соединяющих их ребер. При этом любые 2 вершины соединены единственной цепью ребер, т. е. в дереве отсутствуют циклы. Расстояние между вершинами – это сумма длин ребер, входящих в эту цепь.

В основе метода W. Fitch лежит понятие соседства вершин дерева, для понимания которого необходимо рассмотреть условие 4 вершин, которое было впервые сформулировано Е. А. Смоленским [3] и А. К. Зарецким [11, а затем переоткрыто P. Bunneman [5, 6] и J. Dobson [9].

Теорема Смоленского – Зарецкого. Матрица расстояний между висячими вершинами дерева определяет его с точностью до вершин степени 2 и ребер нулевой длины; причем произвольная матрица расстояний может быть точно реализована аддитивным деревом тогда и только тогда, когда она удовлетворяет условию 4 вершин: для любых различных видов i, j, k, l из 3 сумм расстояний d_ij +d_kl, d_ik+ d_jl и d_il + d_jk 2 равны и не меньше третьей.

Для того чтобы понять смысл условия 4 вершин, достаточно зафиксировать в произвольном дереве 4 различные вершины i, j, k, l и рассмотреть поддерево Т (i, j, k, l), образованное простыми цепями, соединяющими вершины i, j, k, l между собой. Легко видеть, что оно с точностью до вершин степени 2 совпадает с одним из деревьев на рисунке. Пусть для определенности оно совпадает с Т₁. Тогда

d_ij+d_kl < d_ik+d_jl = d_il+d_jk

и общее значение сумм d_lk+d_jl, d_ii+d_ik больше суммы d_ij+d_kl на удвоенную длину центрального ребра в T₁. Равенство же всех 3 сумм соответствует вырожденному случаю, когда длина центрального ребра равна 0 и Т (i, j, k, l) совпадает с T₄ на рисунке.

Будем называть соседними те вершины в дереве, путь между которыми составлен минимальным числом эле ментов дерева: 1 внутренней вершиной и 2 ребрами. Например, на рисунке соседними будут вершины i. j и k, l. Toгда очевидно, что на языке соотношения 4 вершин соседство означает вхождение расстояний между такими парами в левую, меньшую сумму, так как в отличие от всех остальных расстояний в расстояние между соседями не входит длина центрального (внутреннего) ребра. Итак, пользуясь соотношением 4 вершин, можно заранее, не зная дерева, определить по расстояниям между висячими вершинами, какие пары являются соседними.

Очевидно, что вхождение некоей пары i, j в отношение соседства зависит от того, в составе какой четверки видов мы рассматриваем это отношение. Определим теперь так называемую матрицу степеней соседства [15]. Матрицей степеней соседства будем называть числовую матрицу DN= || dn_ij || , в которой dn_ij равно числу четверок, в составе которых пара i, j входила в отношение соседства.

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

Теорема Смоленского – Зарецкого и соотношение 4 вершин (1) справедливы для так называемых аддитивных матриц расстояний и являются необходимым и достаточным условием аддитивности. Однако, как уже указывалось во введении, в подавляющем числе реальных случаев матрицы расстояний не являются аддитивными, и, следовательно, соотношение (1) нарушается хотя бы для одной четверки. Однако очевидно, что в любом случае 4 вида можно обозначить буквами i, j, k, l так, что

           d_ij + d_kl £  min (d_ik + d_jl , d_il + d_jk) _.            (2)

           d_ij + d_kl £  d_ik + d_jl = d_il + d_jk                     (3)

и поэтому называется ослабленным условием 4 вершин [15]. Пользуясь этой очевидной аналогией с аддитивным случаем, будем попрежнему называть пары i, j и k, l, удовлетворяющие соотношению (2), соседями.

W. Fitch предложил в качестве дерева, наиболее соответствующего матрице расстояний D, брать Т, для которого функция |DN (D) – DN (T)|, равная сумме модулей разности между соответствующими элементами матриц степеней соседства, минимальна.

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

4 093 236 352 дерева, если мы допускаем произвольные филогенетические деревья) [12]. И, наконец, не доказано (хотя, по всей видимости, это так), что матрица степеней соседства однозначно определяет топологию дерева, т. е., работая методом W. Fitch, мы не можем гарантировать единственного решения даже для аддитивных данных. Поэтому топологический метод W. Fitch практического применения не нашел.

Принцип максимального топологического подобия. Математический аппарат и формулировка. Чтобы решить задачу построения дерева с оптимальной топологией, необходимо создать некоторый аппарат для характеризации топологии деревьев и соотнесения между собой деревьев и матриц взаимных расстояний. W. Fitch [10] воспользовался для этого матрицами степеней соседства (см. предыдущий раздел), однако этот способ не является единственным или самым удачным. Помимо уже упоминавшейся недоказанности однозначности соответствия матрицы степеней соседства и топологии дерева, очевидно, что такая матрица лишь очень грубо характеризует топологию дерева. Существенно более тонким способом описания топологии дерева является рассмотрение соотношения 4 вершин для каждой четверки видов из набора. Из теоремы Смоленского – Зарецкого следует, что если нас интересует только топология поддерева Т (i, j, k, l) [структура Т (i, j, k, l) с точностью до вершин степени 2 и ребер длины 0), а не конкретные значения длин его ребер, то нам достаточно знать только характер соотношений между суммами d_ij+d_kl, d_ik+d_jl,, d_il+d_jk, а не конкретные значения входящих в эти суммы расстояний.

Оказывается, что аналогичное утверждение справедливо и для произвольного дерева. А именно, если нас интересует топология дерева, а не конкретные значения длин его ребер, то, как показано в работе Н. Colonius и Н. Schulze [8], достаточно знать не саму матрицу расстояний между висячими вершинами дерева, а только характер соотношений между суммами d_ij+d_kl , d_ik+d_jl , d_il+d_jk для каждой четверки висячих вершин. Иными словами, для задания топологии дерева достаточно знать топологию поддеревьев, образованных каждой четверкой (i,j,k,l).

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

F_T (i, j, k, l) = 1, если поддерево Т (i, j, k, l) совпадает с Т₁ на рисунке;

F_T (i, j, k, l)=0, если поддерево Т (i, j, k, l) совпадает c Т₄; во всех остальных случаях функция не определена. Из условия 4 вершин следует, что функции F_T можно дать другое, эквивалентное, определение:

F_T(i, j, k, l)=1, если выполнено условие (1); F_T(i, j, k, l)=0, если все 3 суммы из (1) равны; во всех остальных случаях функция не определена.

Легко видеть, что F_T удовлетворяет следующим условиям:

I. Если F_T определена хоть на одном из наборов ijkl, klij, lkij, то она определена на всех 3 и на всех принимает одно и то же значение.

II. Если F_T определена хоть на одном из наборов ijkl, ikjl, iljk, то она либо определена ровно на одном из них и равна на нем 1, либо она определена на всех 3 и равна на них 0.

Пусть заданы конечное множество видов S и не всюду определенная на множестве четверок из S функция F, принимающая значения 0 и 1 и удовлетворяющая условиям I и II. Будем говорить, что F реализуется деревом, если существует дерево Т с множеством висячих вершин S, такое, что F=F_T. Н. Colonius и Н. Schulze [81 нашли критерий реализуемости функции F деревом и показали, что такая реализация единственна. Этот критерий достаточно громоздок и не дает явного способа построения дерева, реализующего функцию F. Имеется более простая характеристика реализуемых деревьями функций, лежащая в .основе описанных дальше алгоритмов. А именно справедлива следующая теорема, которую мы дадим без доказательства.

Теорема. Функция F реализуется деревом тогда и только тогда, когда из условия: F (i, j, k, l) и F (i, k, l, m) определены, следует, что F (j, k, l, m) определено и равно F (i, k, l, m).

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

Подобно тому, как это было сделано в предыдущем параграфе, перейдём теперь к неаддитивному случаю и рассмотрим неаддитивную матрицу расстояний D. Определим функцию F_D следующим образом: функция F_D (i, j, k, l) определена тогда и только тогда, когда имеет место (2); причем F_D(i, j, k, l) = 1, когда неравенство в (2) строгое, и F_D(i, j, k, l)=0, когда в (2) имеет место равенство.

Ясно, что функция F_D удовлетворяет условиям III. Поэтому, если 2 такие функции F_D и F_D' совпадают на некотором наборе ijkl, то они совпадают на всех наборах, полученных из ijkl перестановкой переменных. Это позволяет ввести для таких функций расстояния \F_DF_D'\ как число различных четверок (i, j, k, l), на которых F_D не равно F_D'.

Ясно, что если функция F_D реализуется некоторым деревом, то это дерево единственное с точностью до вершин степени 2 и ребер нулевой длины, и функции F_D и F_T совпадают.

Поэтому представляется естественным решением в качестве дерева, наиболее соответствующего матрице расстояний, брать такое дерево, для которого |F_D–F_T| минимально. Величину |F_D–F_T |, равную числу четверок, для которых значения F_D и F_T не совпадают, будем далее называть топологическим несовпадением.

Пусть некая матрица аддитивна и пусть для какойлибо четверки {i, j, k, 1} из 3 сумм s₁=d_ij+d_kl, s₂=d_ik+ d_jl и s₃=d_il+d_jk 2, скажем s₁ и s₂ , равны и много больше 3й, тогда любая малая погрешность вычисления s₁ или s₂ или входящих в него расстояний нарушает аддитивность матрицы, но не меняет значения функции F_D и, следовательно, не нарушает ее реализуемости деревом. Таким образом, класс матриц, для которых F_D реализуется деревом, шире класса аддитивных матриц.

4. Функция |F_D–F_T| дает простой объективный способ оценки соответствия структуры построенного дерева исходной матрице расстояний. Это, в частности, позволяет сравнивать между собой филогенетические деревья, построенные по разным критериям, т. е. позволяет решать задачу, которая ранее осуществлялась путем экспертной оценки специалистами.

5. Сравнение функций F_D и F_T на всех наборах четверок, включающих какойлибо интересующий нас вид, позволяет получить количественную оценку надежности его помещения в конкретное положение на дереве в виде величины локального топологического несовпадения. Иными словами, появляется возможность обнаруживать места в построенных деревьях, которые требуют более осторожной трактовки.

7. В отличие от топологического метода W. Fitch принцип максимального топологического подобия позволяет в явной форме получить алгоритмы построения деревьев. 2 алгоритма, реализующие принцип максимального топологического подобия, примеры, иллюстрирующие сформулированные выше преимущества, а также обсуждение биологической состоятельности предлагаемого принципа будут приведены в сопутствующей работе [4].

Поступила 18.06.87

The paper deals with the problem of phylogenetic reconstruction on the basis of comparative analysis of features. Main attention is paid to comparison and classification of the biopolymer sequences. Different approaches to this task are critically reviewed. The novel principle of construction of treelike classification schemes permitting subsequent evolutionary analysis is proposed. It concentrates on reconstruction of the tree with a topologic structure that is most close to topologic features, imprinted in the source distance matrix. Realization of this approach was made possible by development of the special formalism, enabling evaluation and comparison of topologic features of distance matrices and trees.