A fast algorithm for the computation and enumeration of perfect phylogenies when the number of character states is fixed

Sampath Kannan, Tandy Warnow

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

Abstract

The Perfect Phylogeny Problem is a classical problem in computational evolutionary biology, in which a set of species/taxa is described by a set of qualitative characters. In recent years, the problem has been shown to be NP-Complete in general, while the different fixed parameter versions can each be solved in polynomial time. In particular, Agarwala and Fernandez-Baca have developed an O(23r (nk3 + k4)) algorithm for the perfect phylogeny problem for n species defined by k r-state characters. Since commonly the character data is drawn from alignments of molecular sequences, k is the length of the sequences and can thus be very large (in the hundreds or thousands). Thus, it is imperative to develop algorithms which run efficiently for large values of k. In this paper we make additional observations about the structure of the problem and produce an algorithm for the problem that runs in time O(22rk2n). We also show how it is possible to efficiently build a structure that implicitly represents the set of all perfect phylogenies, and to randomly sample from that set.

Original languageEnglish (US)
Title of host publicationProceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
PublisherAssociation for Computing Machinery
Pages595-603
Number of pages9
ISBN (Electronic)0898713498
StatePublished - Jan 22 1995
Externally publishedYes
Event6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 - San Francisco, United States
Duration: Jan 22 1995Jan 24 1995

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
CountryUnited States
CitySan Francisco
Period1/22/951/24/95

Fingerprint

Phylogeny
Enumeration
Fast Algorithm
Polynomials
Biology
Character
Polynomial time
Alignment
NP-complete problem

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Kannan, S., & Warnow, T. (1995). A fast algorithm for the computation and enumeration of perfect phylogenies when the number of character states is fixed. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 (pp. 595-603). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery.

A fast algorithm for the computation and enumeration of perfect phylogenies when the number of character states is fixed. / Kannan, Sampath; Warnow, Tandy.

Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995. Association for Computing Machinery, 1995. p. 595-603 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

Kannan, S & Warnow, T 1995, A fast algorithm for the computation and enumeration of perfect phylogenies when the number of character states is fixed. in Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 595-603, 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995, San Francisco, United States, 1/22/95.
Kannan S, Warnow T. A fast algorithm for the computation and enumeration of perfect phylogenies when the number of character states is fixed. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995. Association for Computing Machinery. 1995. p. 595-603. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
Kannan, Sampath ; Warnow, Tandy. / A fast algorithm for the computation and enumeration of perfect phylogenies when the number of character states is fixed. Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995. Association for Computing Machinery, 1995. pp. 595-603 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
@inproceedings{0ca366e7aefe4468b25b496ac0d09856,
title = "A fast algorithm for the computation and enumeration of perfect phylogenies when the number of character states is fixed",
abstract = "The Perfect Phylogeny Problem is a classical problem in computational evolutionary biology, in which a set of species/taxa is described by a set of qualitative characters. In recent years, the problem has been shown to be NP-Complete in general, while the different fixed parameter versions can each be solved in polynomial time. In particular, Agarwala and Fernandez-Baca have developed an O(23r (nk3 + k4)) algorithm for the perfect phylogeny problem for n species defined by k r-state characters. Since commonly the character data is drawn from alignments of molecular sequences, k is the length of the sequences and can thus be very large (in the hundreds or thousands). Thus, it is imperative to develop algorithms which run efficiently for large values of k. In this paper we make additional observations about the structure of the problem and produce an algorithm for the problem that runs in time O(22rk2n). We also show how it is possible to efficiently build a structure that implicitly represents the set of all perfect phylogenies, and to randomly sample from that set.",
author = "Sampath Kannan and Tandy Warnow",
year = "1995",
month = "1",
day = "22",
language = "English (US)",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery",
pages = "595--603",
booktitle = "Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995",

}

TY - GEN

T1 - A fast algorithm for the computation and enumeration of perfect phylogenies when the number of character states is fixed

AU - Kannan, Sampath

AU - Warnow, Tandy

PY - 1995/1/22

Y1 - 1995/1/22

N2 - The Perfect Phylogeny Problem is a classical problem in computational evolutionary biology, in which a set of species/taxa is described by a set of qualitative characters. In recent years, the problem has been shown to be NP-Complete in general, while the different fixed parameter versions can each be solved in polynomial time. In particular, Agarwala and Fernandez-Baca have developed an O(23r (nk3 + k4)) algorithm for the perfect phylogeny problem for n species defined by k r-state characters. Since commonly the character data is drawn from alignments of molecular sequences, k is the length of the sequences and can thus be very large (in the hundreds or thousands). Thus, it is imperative to develop algorithms which run efficiently for large values of k. In this paper we make additional observations about the structure of the problem and produce an algorithm for the problem that runs in time O(22rk2n). We also show how it is possible to efficiently build a structure that implicitly represents the set of all perfect phylogenies, and to randomly sample from that set.

AB - The Perfect Phylogeny Problem is a classical problem in computational evolutionary biology, in which a set of species/taxa is described by a set of qualitative characters. In recent years, the problem has been shown to be NP-Complete in general, while the different fixed parameter versions can each be solved in polynomial time. In particular, Agarwala and Fernandez-Baca have developed an O(23r (nk3 + k4)) algorithm for the perfect phylogeny problem for n species defined by k r-state characters. Since commonly the character data is drawn from alignments of molecular sequences, k is the length of the sequences and can thus be very large (in the hundreds or thousands). Thus, it is imperative to develop algorithms which run efficiently for large values of k. In this paper we make additional observations about the structure of the problem and produce an algorithm for the problem that runs in time O(22rk2n). We also show how it is possible to efficiently build a structure that implicitly represents the set of all perfect phylogenies, and to randomly sample from that set.

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

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

M3 - Conference contribution

AN - SCOPUS:85010171599

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 595

EP - 603

BT - Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995

PB - Association for Computing Machinery

ER -