INFERRING EVOLUTIONARY HISTORY FROM DNA-SEQUENCES

Authors
KANNAN SK WARNOW TJ
Citation
Sk. Kannan et Tj. Warnow, INFERRING EVOLUTIONARY HISTORY FROM DNA-SEQUENCES, SIAM journal on computing, 23(4), 1994, pp. 713-737
Citations number
29
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
23
Issue
4
Year of publication
1994
Pages
713 - 737
Database
ISI
SICI code
0097-5397(1994)23:4<713:IEHFD>2.0.ZU;2-9
Abstract
One of the longstanding problems in computational molecular biology is the Character Compatibility Problem, which is concerned with the cons truction of phylogenetic trees for species sets, where the species are defined by characters. The character compatibility problem is NP-Comp lete in general. In this paper an O(n2k) time algorithm is described f or the case where the species are described by quaternary characters. This algorithm can be used to construct phylogenetic trees from DNA se quences.