The application of chordal graphs to inferring phylogenetic trees of languages

Proceedings of the 5th International Joint Conference on Natural Language Processing, pages 545–552, Chiang Mai, Thailand, November 8 – 13, 2011. c⃝2011 AFNLP The application of chordal graphs to inferring phylogenetic trees of languages Jessica Enright and Grzegorz Kondrak Department of Computing Science University of Alberta Edmonton, AB, T6G 2E8, Canada {enright,kondrak}@cs.ualberta.ca Abstract Phylogenetic methods are used to build evolutionary trees of languages given character data that may include lexical, phonological, and morphological informa- tion. Such data rarely admits a perfect phylogeny. We explore the use of the more permissive conservative Dollo phy- logeny as an alternative or complementary approach. We propose a heuristic search algorithm based on the notion of chordal graphs. We test this approach by generat- ing phylogenetic trees from three datasets, and comparing them to those produced by other researchers. 1 Introduction Reconstructing the histories of language families is one of the principal tasks of historical linguis- tics. A linguistic phylogenetic tree conveys the evolution of a language family. The family tree can be constructed on the basis of characteris- tics that are common to sets of languages. which include lexical, phonological, and morphologi- cal affinities. Of particular importance are cog- nates — words that originate from the same an- cestral word, and are distinct from words that are “borrowed”, i.e. transferred between languages at some point in history. For example, English brother is cognate with German bruder and Rus- sian brat, all of which come from a Proto-Indo- European word reconstructed as bhr¯ater, while cousin is a borrowing from French. The task of inferring phylogenetic trees of lan- guages is complicated by the pervasiveness of bor- rowings, which frequently occur when languages are in close contact. For example, English is a Germanic language but the majority of its vocab- ulary is borrowed from other branches of Indo- European. Several approaches have been proposed to incorporate borrowings into the tree building process (Minett and Wang, 2003). In particu- lar, Nakhleh et al. (2005a) introduce the concept of a phylogenetic network, which is obtained by augmenting a putative tree with edges represent- ing contact between languages. They present a method to calculate the minimum number of bor- rowings required to admit that tree. However, the method does not actually construct a tree from the data, and it may be computationally intractable when the number of borrowings is large. In this paper, we propose to apply a conservative Dollo phylogeny (CDP) as a model of linguistic phylogenetics. The approach was originally devel- oped by Przytycka et al. (2006) in computational biology. Since it is NP-Hard to compute the mini- mum number of deletions required for a dataset to conform to a CDP (Lewis and Yannakakis, 1980), we propose a heuristic search algorithm based on the notion of chordal graphs. Our algorithm pro- duces an output tree that minimizes the number of borrowings directly from the data. In addition, it has the potential of being significantly faster to compute than the more commonly known perfect phylogeny. Our approach produces …

Content truncated to 500 words