Inferring evolutionary history from DNA sequences

Sampath Kannan, Tandy Warnow

Research output: Contribution to journalConference articlepeer-review


Two related problems are considered. The first is determining whether it is possible to triangulate a vertex-colored graph without introducing edges between vertices of the same color. This is related to a fundamental problem for geneticists, that of using character state information to construct evolutionary trees. The polynomial equivalence of these problems is demonstrated. An important subproblem arises when the characters are based on DNA sequences. Such characters assume up to four states. An O(n2k) algorithm, where n is the number of species and k is the number of characters, is presented for this case.

Original languageEnglish (US)
Pages (from-to)362-371
Number of pages10
JournalIEEE Transactions on Industry Applications
Issue number1 pt 1
StatePublished - Jan 1991
Externally publishedYes
Event1989 Industry Applications Society Annual Meeting - San Diego, CA, USA
Duration: Oct 1 1989Oct 5 1989

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Industrial and Manufacturing Engineering
  • Electrical and Electronic Engineering


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

Cite this