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
Issue number4
StatePublished - Jan 1 1994

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Inferring evolutionary history from DNA sequences'. Together they form a unique fingerprint.

  • Cite this