Обзор методов филогенетической реконструкции языков

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Обзор методов филогенетической реконструкции языков

С.В. Русаков, Д.М. Нурбакова

Пермский государственный национальный

исследовательский университет

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

Ключевые слова: эволюция языков; филогенетика; моделирование эволюции; типология; многомерный статистический анализ.

S.V. Rusakov, D.M. Nurbakova

The overview of the methods of the reconstruction of language phylogenies

A phylogeny of languages can be modeled using different methods of phylogenetic reconstruction. In this paper the overview of the general methods of phylogenetic reconstruction is given.

Key words: language evolution; phylogenetics; evolution modeling; typology; multi-dimensional statistical analysis.

Введение

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

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

Филогенетическое дерево (эволюционное дерево, дерево жизни) - дерево, отражающее эволюционные взаимосвязи между различными видами или другими сущностями, имеющими общего предка. Вершины филогенетического дерева делятся на три класса: листья, узлы и корень (максимум один). Листья -- это конечные вершины, т.е. те, в которые входят ровно по одному ребру; каждый лист отображает некоторый вид живых организмов (или иной объект, подверженный эволюции, например, домен белка). Каждый узел представляет эволюционное событие: разделение предкового вида на два или более, которые в дальнейшем эволюционировали независимо. Корень представляет общего предка всех рассматриваемых объектов. Рёбра филогенетического дерева принято называть “ветвями”. Взаимное расположение ветвей называется топологией.

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

Процесс лингвистической филогенетической реконструкции может быть условно поделён на следующие этапы:

1) выбор данных, наилучшим образом отражающих анализируемый процесс;

2) выбор метода филогенетической реконструкции;

3) выбор способа представления результатов (например, в статистических методах в качестве финального результата часто строится консенсусное дерево);

4) сравнение результатов с результатами, полученными другими методами;

5) анализ результатов с лингвистической и экстралингвистической точек зрения.

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

1) учет заимствований или нет;

2) независимость эволюции разных объектов или нет;

3) идентичность эволюции разных объектов или нет;

4) учет гомоплазии (обратной мутации и/или параллельной эволюции) или нет;

5) эволюция в соответствии с моделью молекулярных часов или нет.

Кроме того, модели различаются в зависимости от того, используются данные одного типа или нет.

В данной статье рассматриваются две группы методов филогенетической реконструкции (дистанционно-матричные и статистические).

1. Методы филогенетической реконструкции

Выделяются две основные группы методов филогенетической реконструкции:

1) дистанционно-матричные;

2) статистические.

1.1. Дистанционно-матричные методы

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

Данная проблема связана с тем, что происходит попарное сравнение, а также с тем, что у разных языков коэффициент сохранения различен (retention rate). Отмечается также, что, ввиду того что происходит переход от дискретных признаков к матрице расстояний, конкретные объекты теряют свои взаимоотношения с деревом, а в случае сложных отношений между таксонами мера расстояния может быть непоказательной и противоречивой. Тем не менее важно отметить, что дистанционные матрицы с достаточно высокой степенью отражают филогенетическую информацию (например, см. [1, 2]).

1.1.1. Метод невзвешенного попарного среднего

Метод невзвешенного попарного среднего, UPGMA (unweighted pair grouping method of agglomeration) [3] - метод иерархической кластеризации. Исходит из предположения о постоянной скорости эволюции. Этот метод хорошо применим в случае, когда процесс эволюции подчиняется закону лексических часов (lexical clock). Часто используется в лексикостатистике. В качестве меры расстояния используется расстояние Хемминга (Hamming Distance) и формируется матрица расстояний. Расстояние между двумя группами последовательностей равно среднему от коэффициентов сходства каждой последовательности из одной группы с каждой последовательностью из другой. Существует алгоритм построения дерева данным методом со сложностью .

1.1.2. Метод связывания ближних соседей

Метод связывания ближних соседей, NeighbourJoining (NJ) [4] агломеративный метод кластерного анализа, используемый в биоинформатике, способный реконструировать филогенетические связи даже в случае невыполнения предположения молекулярных часов. В работах [5, 6] авторы предлагают использовать скорректированное расстояние D(i,j) между парой языков i и j, которое вычисляется через скорректированные расстояния для единиц каждого типа (т.е. медленных лексем (slow lexical) - SL, средних лексем (medium lexical) - ML, быстрых лексем (fast lexical) - FL, морфологических единиц (morphological) - Mo):

(1.1)

филогенетическая реконструкция язык

· - число элементов в классе X, где X принимает значение одного из классов единиц;

·

· - расстояние Хемминга между языками i и j для класса X.

Данный метод является весьма затратным.

1.1.3. Метод построения филогенетической сети на основе связывания соседей

Метод построения филогенетической сети на основе связывания соседей, NeighbourNet [7] - метод, с помощью которого на основе множества разветвлений генерируется сеть. Метод начинает работать с одной вершиной для каждого языка, а затем рассчитывается матрица расстояний, на основе которой определяются соседи. На каждой итерации алгоритм обрабатывает одну пару вершин. Главное отличие этого метода от UPGMA или NJ состоит в том, что вершины объединяются не тогда, когда находится пара ближайших вершин, а когда находится тройка. Лишь после этого происходит сокращение и перерасчет матрицы расстояний.

1.2. Статистические методы

Статистические, или дискретные, методы имеют дело непосредственно с таксонами (с последовательностями данных), а не с их мерами сходства. Большинство дискретных методов используют модели обратимости времени. Данные методы вычисляют неукорененные деревья и добавляют корневую вершину по завершении анализа. Поскольку данная группа методов имеет дело непосредственно с последовательностями данных, а не с мерами сходства, как дистанционные методы, то связь таксонов и дерева не теряется. Тем не менее важно отметить, что с использованием этих методов возрастает неопределённость, поскольку даже сами данные являются точно неопределенными и могут быть ошибочными. Возникающую неопределённость нельзя не учитывать. Для решения этого вопроса разрабатываются различные методы, в частности консенсусные деревья, проверка гипотез о равно экономичных (парсимоничных) деревьях и о случайных выборках "лучших" деревьев [8]. Однако это не позволяет избежать всех возможных проблем. Стоит отметить, что большинство из методов данной группы являются NP-сложными. Примерами данных методов могут служить метод максимальной экономии (парсимонии) (см. [9-12]), метод максимального правдоподобия [5, 13], метод максимальной взвешенной совместимости [5, 6], метод Байеса [8, 11].

1.2.1. Метод максимальной парсимонии

Метод максимальной парсимонии (или экономии), Maximum Parsimony (MP) - это оптимизационная задача нахождения топологии дерева с минимальным числом замен состояний признаков в наиболее информативных положениях (см. [9-12]). Метод основывается на предположении о том, что эволюция “экономна”. Полученное таким образом дерево не всегда является единственным, и, строго говоря, существует множество деревьев, удовлетворяющих гипотезам "правильной филогении". Поэтому в качестве результата часто возвращают консенсусное дерево. Данный метод использует такой критерий оптимальности, как минимальное число трансформаций объектов. Метод работает непосредственно с дискретными данными, и поэтому учитывает информацию, заложенную внутри. Данный метод применяется в предположении примерно одинаковой скорости эволюции. Модификацией МР-метода служит его взвешенный вариант - метод взвешенной максимальной экономии, weighted maximum parsimony (WMP). Каждому объекту присваиваются веса, и производится поиск дерева с минимальным взвешенным числом замен. Обе эти задачи являются NP-сложными. В [10] авторы доказывают, что в случае фиксированного дерева с помеченными вершинами-листьями задача решается за полиномиальное время. В случае конфликтных ситуаций, например при гомопластичных данных, выбирается дерево, которое наилучшим образом подходит всем таксонам, в предположении, что некоторые таксоны могут быть шумом. Часто применяется бутстреп-анализ.

1.2.2. Метод максимальной взвешенной совместимости

Метод максимальной взвешенной совместимости, Weighted Maximum Compatibility (WMC) [5, 6] - это оптимизационная задача поиска дерева с максимальным взвешенным числом совместимости. Это число находится как сумма весов всех последовательностей, совместимых с деревом (в случае, когда объекты эволюционируют без гомоплазии). В общем случае это NP-сложная задача. Одно из решений заключается в предварительном проведении анализа методом максимальной взвешенной экономии, в результате которого получаются оптимальные WMP-деревья, которые затем проверяются по критерию WMC. В качестве результата возможны несколько деревьев, поэтому зачастую возвращают консенсусное дерево.

1.2.3. Метод максимального правдоподобия

Метод максимального правдоподобия, Maximum Likelihood (ML) - стохастический оптимизационный метод. Метод применяют, если имеется информация о закономерностях эволюционных преобразований признаков и известно распределение состояний признаков у изучаемых объектов (например, в [5, 13] используется Пуассоновский процесс). Рассчитываются вероятности анцестральных состояний и вероятности различных эволюционных траекторий, которые могли привести к современным формам.

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

1.2.4. Метод Байеса

Метод Байеса, Bayesian estimation [8, 11] - стохастический метод, основанный на расчете постериорной вероятности вершины, отражающей отношение вероятности появления дерева в выборке с данной вершиной. Выборка содержит наиболее часто встречаемые деревья. Постериорная вероятность рассчитывается на основе априорной вероятности и вероятности истинности данных. Постериорная вероятность дерева считается по формуле

, (1.2)

· - условная вероятность появления дерева T_i при условии M;

· M - матрица данных размерности x, где n - число рассматриваемых языков, а k - число значений m_i. Каждый элемент матрицы M представляет собой численный код, соответствующий словоформе n-го языка, выражающей текущее значение. Значение может быть описано с помощью когнат или нет. Когнатам присваиваются одинаковые коды. Таким образом, "состояния" значения соответствуют некогнатным формам;

· - априорная вероятность дерева T_i;

· - вероятность данных при условии дерева T_i (если значения независимы друг от друга):

; (1.3)

· - вероятность того, что словоформы из M эволюционируют вдоль данного филогенетического дерева:

(1.4)

где

· t - длина ветви;

· p(t) - априорная вероятность значения длины ветви;

· p(Q) - априорная вероятность параметра модели;

· - матрица изменений значений, составляемая для каждого значения, имеющего s состояний q_ij, отражает величину мгновенного изменения состояния i на состояние j.

Элементы главной диагонали равны , устанавливаются таким образом, чтобы сумма элементов строки была равна 0.0.

. (1.5)

Для расчета постериорной вероятности распределения деревьев используется метод Марковские цепи Монте-Карло (Markov Chain Monte Carlo, MCMC). Состояние цепи соответствуют различным филогенетическим деревьям. Для семплирования используется алгоритм Метрополиса-Гастингса (например, см. [14]).

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

2. Филогенетическая сеть

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

Цель филогенетической сети - отражение не только генетических отношений между языками (или другими объектами), но и, например, процессов заимствования (например, см.[15]). При построении филогенетической сети исходят из предположения о том, что эволюция имеет не древовидную структуру. Филогенетическая сеть чаще всего представляет собой неукорененное дерево, содержащее дополнительные ветви, отражающие заимствования или гомоплазию. Филогенетические сети не всегда планарны.

Обзор филогенетических сетей представлен в [16]. Для их построения используются не только дистанционно-матричные методы, как, например, NeighbourNet, но и статистические (парсимоничные сети, медианные сети, сетевой метод).

Заключение

Таким образом, были представлены основные методы филогенетической реконструкции. Они поделены на две группы в зависимости от используемой концепции: дистанционно-матричные (например, Neighbour Joining, UPGMA, NeighbourNet) и статистические (например, метод Байеса, максимальной парсимонии, максимального правдоподобия). Методы обеих групп имеют свои достоинства и недостатки. Выбор метода осуществляется в зависимости от данных и ограничений модели.

Список литературы

Bryant D., Huson D., Kloepper T., Nieselt-Struwe K. Distance corrections on recombinant sequences // Benson G. and R. Page. 2003. WABI 2003: Algorithms in Bioinformatics, Third International Works-hop, Proceedings. Lecture Notes in Computer Science 2812. P. 271-286.

Legendre P., Makarenkov V. Reconstruction of biogeographical and evolutionary net-works using reticulograms // Systematic Biology. 2002. Vol. 51. P. 199-216.

Sokal R., Michener C. A statistical method for evaluating systematic relationships // University of Kansas Science Bulletin. 1958. Vol. 38. P. 1409-1438.

Nei M., Saitou N. The neighbor-joining method: a new method for reconstructing phylogenetic trees // Molecular Biology and Evolution. Vol. 4 (4). P. 406-425.

Barbanзon F., Warnow T., Evans S., Ringe D., Nakhleh L. An experimental study compa-ring linguistic phylogenetic recon-struction methods // Languages and Genes. UC Santa Barbara: Cambridge University Press, 2007.

Nakhleh L., Warnow T., Ringe D., Evans S.N. A Comparison of Phylogenetic Reconstruc-tion Methods on an IE Dataset // The Transactions of the Philological Society. 2005. Vol. 3(2). P. 171-192.

Moulton V., Bryant D. NeighbourNet: An Agglomerative Method for the Recon-struction of Phylogenetic Network // Molecular Biology and Evolution. Feb 2004. Vol. 2 (21). P. 255-6.

Pagel M, Meade A. Bayesian estimation of correlated evolution across cultures: A case study of marriage systems and wealth transfer at marriage // Holden C.J., Shennan S., Mace R. The Evolution of Cultural Diversity: a phylogenetic approach. 2005. P.235-256.

Darlu P., Tassy P. La Reconstruction Phylogйnйtique. Concepts et Mйthodes. 2004. P. 31-145, 195-225.

Nakhleh L., Jin G., Zhao F. Mellor-Crummey Reconstruction Phylogenetic Networks Using Maximum Parsimony // Proceedings of 2005 IEEE Computational Systems Bioinformatics Conference. 2005. P. 93-102.

Meade A., Pagel M. Comparison of maximum parsimony and Bayesian Bantu language trees // Holden C.J., Shennan S., Mace R. The Evolution of Cultural Diversity: a phylogenetic approach. 2005. P. 53-65.

Sober E. Parsimony in Systematics: Philoso-phical Issues // Annual Review of Ecology and Systematics. 1983. Vol. 14. P. 335-357.

Warnow T., Evans S.N., Ringe D., Nakhleh L. A Stochastic Model Of Language Evolution That Incorporates Homoplasy And Borro-wing // Phylogenetic Methods and the Prehistory of Languages. July 2004. P.1-25.

Chib S., Greemberg E. Understanding the Metropolis-Hastings Algorithm // The American Statistician. November 1995. Vol. 4 (49). P.327-335.

Erdem E., Lifschitz V., Nakhleh L., Ringe D. Reconstructing the Evolutionary History of Indo-European Languages using Answer Set Programming // Proceedings of the Fifth International Symposium on Practical Aspects of Declarative Languages. 2003.

Posada D., and K. Crandall. Intraspecific gene genealogies: trees grafting into networks // Trends in Ecology & Evolution. 2001. Vol.16. P. 37-45.

Размещено на Allbest.ru