Determining the Evolutionary Tree Using Experiments

Sampath K. Kannan, Eugene L. Lawler, Tandy Warnow

Research output: Contribution to journalArticle

Abstract

Evolutionary trees, also known as phylogenetic trees, are rooted vertex-labeled trees which describe the evolution of a species set S from a common ancestor. The determination of evolutionary trees is a fundamental problem in computational evolutionary biology, and has been studied in great depth. In this paper, we present a new model of computation which assumes that it is possible to determine the true evolutionary tree for each three species, perhaps through the use of Ahlquist-Sibley experimental techniques. We present tight upper and lower bounds for constructing evolutionary trees using experiments.

Original languageEnglish (US)
Pages (from-to)26-50
Number of pages25
JournalJournal of Algorithms
Volume21
Issue number1
DOIs
StatePublished - Jul 1996
Externally publishedYes

Fingerprint

Evolutionary Tree
Experiment
Experiments
Labeled Trees
Models of Computation
Phylogenetic Tree
Biology
Upper and Lower Bounds
Vertex of a graph

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Cite this

Determining the Evolutionary Tree Using Experiments. / Kannan, Sampath K.; Lawler, Eugene L.; Warnow, Tandy.

In: Journal of Algorithms, Vol. 21, No. 1, 07.1996, p. 26-50.

Research output: Contribution to journalArticle

Kannan, Sampath K. ; Lawler, Eugene L. ; Warnow, Tandy. / Determining the Evolutionary Tree Using Experiments. In: Journal of Algorithms. 1996 ; Vol. 21, No. 1. pp. 26-50.
@article{06377d196bc04f7f8681404a20911cd2,
title = "Determining the Evolutionary Tree Using Experiments",
abstract = "Evolutionary trees, also known as phylogenetic trees, are rooted vertex-labeled trees which describe the evolution of a species set S from a common ancestor. The determination of evolutionary trees is a fundamental problem in computational evolutionary biology, and has been studied in great depth. In this paper, we present a new model of computation which assumes that it is possible to determine the true evolutionary tree for each three species, perhaps through the use of Ahlquist-Sibley experimental techniques. We present tight upper and lower bounds for constructing evolutionary trees using experiments.",
author = "Kannan, {Sampath K.} and Lawler, {Eugene L.} and Tandy Warnow",
year = "1996",
month = "7",
doi = "10.1006/jagm.1996.0035",
language = "English (US)",
volume = "21",
pages = "26--50",
journal = "Journal of Algorithms",
issn = "0196-6774",
publisher = "Academic Press Inc.",
number = "1",

}

TY - JOUR

T1 - Determining the Evolutionary Tree Using Experiments

AU - Kannan, Sampath K.

AU - Lawler, Eugene L.

AU - Warnow, Tandy

PY - 1996/7

Y1 - 1996/7

N2 - Evolutionary trees, also known as phylogenetic trees, are rooted vertex-labeled trees which describe the evolution of a species set S from a common ancestor. The determination of evolutionary trees is a fundamental problem in computational evolutionary biology, and has been studied in great depth. In this paper, we present a new model of computation which assumes that it is possible to determine the true evolutionary tree for each three species, perhaps through the use of Ahlquist-Sibley experimental techniques. We present tight upper and lower bounds for constructing evolutionary trees using experiments.

AB - Evolutionary trees, also known as phylogenetic trees, are rooted vertex-labeled trees which describe the evolution of a species set S from a common ancestor. The determination of evolutionary trees is a fundamental problem in computational evolutionary biology, and has been studied in great depth. In this paper, we present a new model of computation which assumes that it is possible to determine the true evolutionary tree for each three species, perhaps through the use of Ahlquist-Sibley experimental techniques. We present tight upper and lower bounds for constructing evolutionary trees using experiments.

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

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

U2 - 10.1006/jagm.1996.0035

DO - 10.1006/jagm.1996.0035

M3 - Article

AN - SCOPUS:0030376980

VL - 21

SP - 26

EP - 50

JO - Journal of Algorithms

JF - Journal of Algorithms

SN - 0196-6774

IS - 1

ER -