Constructing evolutionary trees in the presence of polymorphic characters

Maria Bonet, Cynthia Phillips, Tandy Warnow, Shibu Yooseph

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Most phylogenetics literature and construction methods based upon characters presume monomorphism (one state per character per species), and 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, which was presented by invitation at the National Academy of Sciences in November 1995.

Original languageEnglish (US)
Title of host publicationProceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996
PublisherAssociation for Computing Machinery
Pages220-229
Number of pages10
ISBN (Electronic)0897917855
DOIs
StatePublished - Jul 1 1996
Externally publishedYes
Event28th Annual ACM Symposium on Theory of Computing, STOC 1996 - Philadelphia, United States
Duration: May 22 1996May 24 1996

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129452
ISSN (Print)0737-8017

Other

Other28th Annual ACM Symposium on Theory of Computing, STOC 1996
CountryUnited States
CityPhiladelphia
Period5/22/965/24/96

Fingerprint

Polymorphism
Linguistics
Phylogeny

ASJC Scopus subject areas

  • Software

Cite this

Bonet, M., Phillips, C., Warnow, T., & Yooseph, S. (1996). Constructing evolutionary trees in the presence of polymorphic characters. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996 (pp. 220-229). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F129452). Association for Computing Machinery. https://doi.org/10.1145/237814.237867

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

Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996. Association for Computing Machinery, 1996. p. 220-229 (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F129452).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Bonet, M, Phillips, C, Warnow, T & Yooseph, S 1996, Constructing evolutionary trees in the presence of polymorphic characters. in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996. Proceedings of the Annual ACM Symposium on Theory of Computing, vol. Part F129452, Association for Computing Machinery, pp. 220-229, 28th Annual ACM Symposium on Theory of Computing, STOC 1996, Philadelphia, United States, 5/22/96. https://doi.org/10.1145/237814.237867
Bonet M, Phillips C, Warnow T, Yooseph S. Constructing evolutionary trees in the presence of polymorphic characters. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996. Association for Computing Machinery. 1996. p. 220-229. (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/237814.237867
Bonet, Maria ; Phillips, Cynthia ; Warnow, Tandy ; Yooseph, Shibu. / Constructing evolutionary trees in the presence of polymorphic characters. Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996. Association for Computing Machinery, 1996. pp. 220-229 (Proceedings of the Annual ACM Symposium on Theory of Computing).
@inproceedings{8ca77ee505ee44a68ff4e5018dadd812,
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), and 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, which was 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 = "1996",
month = "7",
day = "1",
doi = "10.1145/237814.237867",
language = "English (US)",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",
pages = "220--229",
booktitle = "Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996",

}

TY - GEN

T1 - Constructing evolutionary trees in the presence of polymorphic characters

AU - Bonet, Maria

AU - Phillips, Cynthia

AU - Warnow, Tandy

AU - Yooseph, Shibu

PY - 1996/7/1

Y1 - 1996/7/1

N2 - Most phylogenetics literature and construction methods based upon characters presume monomorphism (one state per character per species), and 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, which was 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), and 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, which was presented by invitation at the National Academy of Sciences in November 1995.

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

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

U2 - 10.1145/237814.237867

DO - 10.1145/237814.237867

M3 - Conference contribution

AN - SCOPUS:0029719647

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 220

EP - 229

BT - Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996

PB - Association for Computing Machinery

ER -