Inferring evolutionary history from DNA sequences

Sampath K. Kannan, Tandy Warnow

Research output: Contribution to journalArticle

Abstract

One of the longstanding problems in computational molecular biology is the Character Compatibility Problem, which is concerned with the construction of phylogenetic trees for species sets, where the species are defined by characters. The character compatibility problem is NP-Complete in general. In this paper an O(n2k) time algorithm is described for the case where the species are described by quaternary characters. This algorithm can be used to construct phylogenetic trees from DNA sequences.

Original languageEnglish (US)
Pages (from-to)713-737
Number of pages25
JournalSIAM Journal on Computing
Volume23
Issue number4
DOIs
StatePublished - Jan 1 1994
Externally publishedYes

Fingerprint

DNA sequences
DNA Sequence
Molecular biology
Phylogenetic Tree
Compatibility
Computational complexity
Computational Molecular Biology
NP-complete problem
History
Character

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Cite this

Inferring evolutionary history from DNA sequences. / Kannan, Sampath K.; Warnow, Tandy.

In: SIAM Journal on Computing, Vol. 23, No. 4, 01.01.1994, p. 713-737.

Research output: Contribution to journalArticle

Kannan, Sampath K. ; Warnow, Tandy. / Inferring evolutionary history from DNA sequences. In: SIAM Journal on Computing. 1994 ; Vol. 23, No. 4. pp. 713-737.
@article{078d0462cfaf42e1937732b577f8e275,
title = "Inferring evolutionary history from DNA sequences",
abstract = "One of the longstanding problems in computational molecular biology is the Character Compatibility Problem, which is concerned with the construction of phylogenetic trees for species sets, where the species are defined by characters. The character compatibility problem is NP-Complete in general. In this paper an O(n2k) time algorithm is described for the case where the species are described by quaternary characters. This algorithm can be used to construct phylogenetic trees from DNA sequences.",
author = "Kannan, {Sampath K.} and Tandy Warnow",
year = "1994",
month = "1",
day = "1",
doi = "10.1137/S0097539791222171",
language = "English (US)",
volume = "23",
pages = "713--737",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "4",

}

TY - JOUR

T1 - Inferring evolutionary history from DNA sequences

AU - Kannan, Sampath K.

AU - Warnow, Tandy

PY - 1994/1/1

Y1 - 1994/1/1

N2 - One of the longstanding problems in computational molecular biology is the Character Compatibility Problem, which is concerned with the construction of phylogenetic trees for species sets, where the species are defined by characters. The character compatibility problem is NP-Complete in general. In this paper an O(n2k) time algorithm is described for the case where the species are described by quaternary characters. This algorithm can be used to construct phylogenetic trees from DNA sequences.

AB - One of the longstanding problems in computational molecular biology is the Character Compatibility Problem, which is concerned with the construction of phylogenetic trees for species sets, where the species are defined by characters. The character compatibility problem is NP-Complete in general. In this paper an O(n2k) time algorithm is described for the case where the species are described by quaternary characters. This algorithm can be used to construct phylogenetic trees from DNA sequences.

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

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

U2 - 10.1137/S0097539791222171

DO - 10.1137/S0097539791222171

M3 - Article

AN - SCOPUS:0028484735

VL - 23

SP - 713

EP - 737

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 4

ER -