The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.1 / (1999))
Constructing Evolutionary Trees in the Presence of Polymorphic Characters
Maria Bonet, Cynthia Phillips, Tandy Warnow, Shibu Yooseph,
Pages. 103-131
Abstract Most phylogenetics literature and construction methods
based upon characters presume monomorphism (one state per
character per species), yet polymorphism (multiple states per
character per species) is well documented in both biology and
historical linguistics. In this paper we consider the problem of
inferring evolutionary trees for polymorphic characters. We show
efficient algorithms for the construction of perfect phylogenies
from polymorphic data. These methods have been used to help
construct the evolutionary tree proposed by Warnow, Ringe, and
Taylor for the Indo-European family of languages and presented by
invitation at the National Academy of Sciences in November 1995.
Contents 1. Introduction 2. Foundations 3. Inferring perfect phylogenies from polymorphic
characters 3.1. Minimum load problems 4. Algorithms for perfect
phylogenies from polymorphic characters 4.1. A combinatorial
algorithm for fixed $k$ and $l$ 4.2. A graph-theoretic algorithm
for fixed $k$ and $l$ 4.2.1. Preliminary definitions 4.2.2.
Characterization of $l$-triangulated graphs 4.2.3.
$l$-triangulating a vertex-colored graph 4.2.4. Summary of the
algorithm to solve the $l$-load perfect phylogeny problem 4.3.
Inferring perfect phylogenies from mixed data 5. Polymorphism in
linguistics 6. Polymorphism in biology 7. Discussion
Key words lgorithms, graphs, evolutionary trees
Mathmatical Subject Classification 05C05, 68Q25, 92-08, 92B05