Estimating large distances in phylogenetic reconstruction

Daniel H. Huson, Kelly Ann Smith, Tandy Warnow

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A major computational problem in biology is the reconstruction of evolutionary (A.K.A. "Phylogenetic") trees from biomolecular sequences. Most polynomial time phylogenetic reconstruction methods are distance-based, and take as input an estimation of the evolutionary distance between every pair of biomolecular sequences in the dataset. The estimation of evolutionary distances is standardized except when the set of biomolecular sequences is "Saturated", which means it contains a pair of sequences which are no more similar than two random sequences. In this case, the standard statistical techniques for estimating evolutionary distances cannot be used. In this study we explore the performance of three important distance-based phylogenetic reconstruction methods under the various techniques that have been proposed for estimating evolutionary distances when the dataset is saturated.

Original languageEnglish (US)
Title of host publicationAlgorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings
PublisherSpringer Verlag
Pages271-285
Number of pages15
Volume1668
ISBN (Print)3540664270, 9783540664277
StatePublished - 1999
Externally publishedYes
Event3rd International Workshop on Algorithm Engineering, WAE 1999 - London, United Kingdom
Duration: Jul 19 1999Jul 21 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1668
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd International Workshop on Algorithm Engineering, WAE 1999
CountryUnited Kingdom
CityLondon
Period7/19/997/21/99

Fingerprint

Phylogenetics
Polynomials
Evolutionary Tree
Phylogenetic Tree
Random Sequence
Biology
Polynomial time

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this

Huson, D. H., Ann Smith, K., & Warnow, T. (1999). Estimating large distances in phylogenetic reconstruction. In Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings (Vol. 1668, pp. 271-285). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1668). Springer Verlag.

Estimating large distances in phylogenetic reconstruction. / Huson, Daniel H.; Ann Smith, Kelly; Warnow, Tandy.

Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings. Vol. 1668 Springer Verlag, 1999. p. 271-285 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1668).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Huson, DH, Ann Smith, K & Warnow, T 1999, Estimating large distances in phylogenetic reconstruction. in Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings. vol. 1668, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1668, Springer Verlag, pp. 271-285, 3rd International Workshop on Algorithm Engineering, WAE 1999, London, United Kingdom, 7/19/99.
Huson DH, Ann Smith K, Warnow T. Estimating large distances in phylogenetic reconstruction. In Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings. Vol. 1668. Springer Verlag. 1999. p. 271-285. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
Huson, Daniel H. ; Ann Smith, Kelly ; Warnow, Tandy. / Estimating large distances in phylogenetic reconstruction. Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings. Vol. 1668 Springer Verlag, 1999. pp. 271-285 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{d269d50d0d0d4372b0e013b3c0fc3af1,
title = "Estimating large distances in phylogenetic reconstruction",
abstract = "A major computational problem in biology is the reconstruction of evolutionary (A.K.A. {"}Phylogenetic{"}) trees from biomolecular sequences. Most polynomial time phylogenetic reconstruction methods are distance-based, and take as input an estimation of the evolutionary distance between every pair of biomolecular sequences in the dataset. The estimation of evolutionary distances is standardized except when the set of biomolecular sequences is {"}Saturated{"}, which means it contains a pair of sequences which are no more similar than two random sequences. In this case, the standard statistical techniques for estimating evolutionary distances cannot be used. In this study we explore the performance of three important distance-based phylogenetic reconstruction methods under the various techniques that have been proposed for estimating evolutionary distances when the dataset is saturated.",
author = "Huson, {Daniel H.} and {Ann Smith}, Kelly and Tandy Warnow",
year = "1999",
language = "English (US)",
isbn = "3540664270",
volume = "1668",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "271--285",
booktitle = "Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings",
address = "Germany",

}

TY - GEN

T1 - Estimating large distances in phylogenetic reconstruction

AU - Huson, Daniel H.

AU - Ann Smith, Kelly

AU - Warnow, Tandy

PY - 1999

Y1 - 1999

N2 - A major computational problem in biology is the reconstruction of evolutionary (A.K.A. "Phylogenetic") trees from biomolecular sequences. Most polynomial time phylogenetic reconstruction methods are distance-based, and take as input an estimation of the evolutionary distance between every pair of biomolecular sequences in the dataset. The estimation of evolutionary distances is standardized except when the set of biomolecular sequences is "Saturated", which means it contains a pair of sequences which are no more similar than two random sequences. In this case, the standard statistical techniques for estimating evolutionary distances cannot be used. In this study we explore the performance of three important distance-based phylogenetic reconstruction methods under the various techniques that have been proposed for estimating evolutionary distances when the dataset is saturated.

AB - A major computational problem in biology is the reconstruction of evolutionary (A.K.A. "Phylogenetic") trees from biomolecular sequences. Most polynomial time phylogenetic reconstruction methods are distance-based, and take as input an estimation of the evolutionary distance between every pair of biomolecular sequences in the dataset. The estimation of evolutionary distances is standardized except when the set of biomolecular sequences is "Saturated", which means it contains a pair of sequences which are no more similar than two random sequences. In this case, the standard statistical techniques for estimating evolutionary distances cannot be used. In this study we explore the performance of three important distance-based phylogenetic reconstruction methods under the various techniques that have been proposed for estimating evolutionary distances when the dataset is saturated.

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

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

M3 - Conference contribution

AN - SCOPUS:84957082913

SN - 3540664270

SN - 9783540664277

VL - 1668

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 271

EP - 285

BT - Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings

PB - Springer Verlag

ER -