Solving large scale phylogenetic problems using DCM2.

D. H. Huson, L. Vawter, Tandy Warnow

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

In an earlier paper, we described a new method for phylogenetic tree reconstruction called the Disk Covering Method, or DCM. This is a general method which can be used with any existing phylogenetic method in order to improve its performance. We showed analytically and experimentally that when DCM is used in conjunction with polynomial time distance-based methods, it improves the accuracy of the trees reconstructed. In this paper, we discuss a variant on DCM, that we call DCM2. DCM2 is designed to be used with phylogenetic methods whose objective is the solution of NP-hard optimization problems. We show that DCM2 can be used to accelerate searches for Maximum Parsimony trees. We also motivate the need for solutions to NP-hard optimization problems by showing that on some very large and important datasets, the most popular (and presumably best performing) polynomial time distance methods have poor accuracy.

Original languageEnglish
Title of host publicationProceedings / . International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology
Pages118-129
Number of pages12
StatePublished - Dec 1 1999
Externally publishedYes

Fingerprint

Datasets

Cite this

Huson, D. H., Vawter, L., & Warnow, T. (1999). Solving large scale phylogenetic problems using DCM2. In Proceedings / . International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology (pp. 118-129)

Solving large scale phylogenetic problems using DCM2. / Huson, D. H.; Vawter, L.; Warnow, Tandy.

Proceedings / . International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology. 1999. p. 118-129.

Research output: Chapter in Book/Report/Conference proceedingChapter

Huson, DH, Vawter, L & Warnow, T 1999, Solving large scale phylogenetic problems using DCM2. in Proceedings / . International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology. pp. 118-129.
Huson DH, Vawter L, Warnow T. Solving large scale phylogenetic problems using DCM2. In Proceedings / . International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology. 1999. p. 118-129
Huson, D. H. ; Vawter, L. ; Warnow, Tandy. / Solving large scale phylogenetic problems using DCM2. Proceedings / . International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology. 1999. pp. 118-129
@inbook{505195570f884384bc30f50474be4300,
title = "Solving large scale phylogenetic problems using DCM2.",
abstract = "In an earlier paper, we described a new method for phylogenetic tree reconstruction called the Disk Covering Method, or DCM. This is a general method which can be used with any existing phylogenetic method in order to improve its performance. We showed analytically and experimentally that when DCM is used in conjunction with polynomial time distance-based methods, it improves the accuracy of the trees reconstructed. In this paper, we discuss a variant on DCM, that we call DCM2. DCM2 is designed to be used with phylogenetic methods whose objective is the solution of NP-hard optimization problems. We show that DCM2 can be used to accelerate searches for Maximum Parsimony trees. We also motivate the need for solutions to NP-hard optimization problems by showing that on some very large and important datasets, the most popular (and presumably best performing) polynomial time distance methods have poor accuracy.",
author = "Huson, {D. H.} and L. Vawter and Tandy Warnow",
year = "1999",
month = "12",
day = "1",
language = "English",
pages = "118--129",
booktitle = "Proceedings / . International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology",

}

TY - CHAP

T1 - Solving large scale phylogenetic problems using DCM2.

AU - Huson, D. H.

AU - Vawter, L.

AU - Warnow, Tandy

PY - 1999/12/1

Y1 - 1999/12/1

N2 - In an earlier paper, we described a new method for phylogenetic tree reconstruction called the Disk Covering Method, or DCM. This is a general method which can be used with any existing phylogenetic method in order to improve its performance. We showed analytically and experimentally that when DCM is used in conjunction with polynomial time distance-based methods, it improves the accuracy of the trees reconstructed. In this paper, we discuss a variant on DCM, that we call DCM2. DCM2 is designed to be used with phylogenetic methods whose objective is the solution of NP-hard optimization problems. We show that DCM2 can be used to accelerate searches for Maximum Parsimony trees. We also motivate the need for solutions to NP-hard optimization problems by showing that on some very large and important datasets, the most popular (and presumably best performing) polynomial time distance methods have poor accuracy.

AB - In an earlier paper, we described a new method for phylogenetic tree reconstruction called the Disk Covering Method, or DCM. This is a general method which can be used with any existing phylogenetic method in order to improve its performance. We showed analytically and experimentally that when DCM is used in conjunction with polynomial time distance-based methods, it improves the accuracy of the trees reconstructed. In this paper, we discuss a variant on DCM, that we call DCM2. DCM2 is designed to be used with phylogenetic methods whose objective is the solution of NP-hard optimization problems. We show that DCM2 can be used to accelerate searches for Maximum Parsimony trees. We also motivate the need for solutions to NP-hard optimization problems by showing that on some very large and important datasets, the most popular (and presumably best performing) polynomial time distance methods have poor accuracy.

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

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

M3 - Chapter

C2 - 10786294

AN - SCOPUS:0033289315

SP - 118

EP - 129

BT - Proceedings / . International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology

ER -