Constructing evolutionary trees in the presence of polymorphic characters

Maria Bonet, Cynthia Phillips, Tandy Warnow, Shibu Yooseph

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)103-131
Number of pages29
JournalSIAM Journal on Computing
Volume29
Issue number1
DOIs
StatePublished - Sep 1999
Externally publishedYes

Fingerprint

Evolutionary Tree
Polymorphism
Linguistics
Monomorphism
Phylogeny
Phylogenetics
Biology
Efficient Algorithms
Character

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Cite this

Constructing evolutionary trees in the presence of polymorphic characters. / Bonet, Maria; Phillips, Cynthia; Warnow, Tandy; Yooseph, Shibu.

In: SIAM Journal on Computing, Vol. 29, No. 1, 09.1999, p. 103-131.

Research output: Contribution to journalArticle

Bonet, Maria ; Phillips, Cynthia ; Warnow, Tandy ; Yooseph, Shibu. / Constructing evolutionary trees in the presence of polymorphic characters. In: SIAM Journal on Computing. 1999 ; Vol. 29, No. 1. pp. 103-131.
@article{4735fca2032a4a9aaa6f7916e4d36dee,
title = "Constructing evolutionary trees in the presence of polymorphic characters",
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.",
author = "Maria Bonet and Cynthia Phillips and Tandy Warnow and Shibu Yooseph",
year = "1999",
month = "9",
doi = "10.1137/S0097539796324636",
language = "English (US)",
volume = "29",
pages = "103--131",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "1",

}

TY - JOUR

T1 - Constructing evolutionary trees in the presence of polymorphic characters

AU - Bonet, Maria

AU - Phillips, Cynthia

AU - Warnow, Tandy

AU - Yooseph, Shibu

PY - 1999/9

Y1 - 1999/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0342298647&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0342298647&partnerID=8YFLogxK

U2 - 10.1137/S0097539796324636

DO - 10.1137/S0097539796324636

M3 - Article

AN - SCOPUS:0342298647

VL - 29

SP - 103

EP - 131

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 1

ER -