Short Quartet Puzzling: A new quartet-based phylogeny reconstruction algorithm

Sagi Snir, Tandy Warnow, Satish Rao

Research output: Contribution to journalArticle

Abstract

Quartet-based phylogeny reconstruction methods, such as Quartet Puzzling, were introduced in the hope that they might be competitive with maximum likelihood methods, without being as computationally intensive. However, despite the numerous quartet-based methods that have been developed, their performance in simulation has been disappointing. In particular, Ranwez and Gascuel, the developers of one of the best quartet methods, conjecture that quartet-based methods have inherent limitations that make them unable to produce trees as accurate as neighbor joining or maximum parsimony. In this paper, we present Short Quartet Puzzling, a new quartet-based phylogeny reconstruction algorithm, and we demonstrate the improved topological accuracy of the new method over maximum parsimony and neighbor joining, disproving the conjecture of Ranwez and Gascuel. We also show a dramatic improvement over Quartet Puzzling. Thus, while our new method is not compared to any ML method (as it is not expected to be as accurate as the best of these), this study shows that quartet methods are not as limited in performance as was previously conjectured, and opens the possibility to further improvements through new algorithmic designs.

Original languageEnglish (US)
Pages (from-to)91-103
Number of pages13
JournalJournal of Computational Biology
Volume15
Issue number1
DOIs
StatePublished - Jan 1 2008
Externally publishedYes

Fingerprint

Phylogeny
Reconstruction Algorithm
Joining
Maximum likelihood
Maximum Parsimony
Maximum Likelihood Method
Demonstrate

Keywords

  • Algorithms
  • Biology
  • Computational molecular biology
  • Evolution

ASJC Scopus subject areas

  • Molecular Biology
  • Genetics

Cite this

Short Quartet Puzzling : A new quartet-based phylogeny reconstruction algorithm. / Snir, Sagi; Warnow, Tandy; Rao, Satish.

In: Journal of Computational Biology, Vol. 15, No. 1, 01.01.2008, p. 91-103.

Research output: Contribution to journalArticle

@article{412af3d572b64ec0b88562d18802b295,
title = "Short Quartet Puzzling: A new quartet-based phylogeny reconstruction algorithm",
abstract = "Quartet-based phylogeny reconstruction methods, such as Quartet Puzzling, were introduced in the hope that they might be competitive with maximum likelihood methods, without being as computationally intensive. However, despite the numerous quartet-based methods that have been developed, their performance in simulation has been disappointing. In particular, Ranwez and Gascuel, the developers of one of the best quartet methods, conjecture that quartet-based methods have inherent limitations that make them unable to produce trees as accurate as neighbor joining or maximum parsimony. In this paper, we present Short Quartet Puzzling, a new quartet-based phylogeny reconstruction algorithm, and we demonstrate the improved topological accuracy of the new method over maximum parsimony and neighbor joining, disproving the conjecture of Ranwez and Gascuel. We also show a dramatic improvement over Quartet Puzzling. Thus, while our new method is not compared to any ML method (as it is not expected to be as accurate as the best of these), this study shows that quartet methods are not as limited in performance as was previously conjectured, and opens the possibility to further improvements through new algorithmic designs.",
keywords = "Algorithms, Biology, Computational molecular biology, Evolution",
author = "Sagi Snir and Tandy Warnow and Satish Rao",
year = "2008",
month = "1",
day = "1",
doi = "10.1089/cmb.2007.0103",
language = "English (US)",
volume = "15",
pages = "91--103",
journal = "Journal of Computational Biology",
issn = "1066-5277",
publisher = "Mary Ann Liebert Inc.",
number = "1",

}

TY - JOUR

T1 - Short Quartet Puzzling

T2 - A new quartet-based phylogeny reconstruction algorithm

AU - Snir, Sagi

AU - Warnow, Tandy

AU - Rao, Satish

PY - 2008/1/1

Y1 - 2008/1/1

N2 - Quartet-based phylogeny reconstruction methods, such as Quartet Puzzling, were introduced in the hope that they might be competitive with maximum likelihood methods, without being as computationally intensive. However, despite the numerous quartet-based methods that have been developed, their performance in simulation has been disappointing. In particular, Ranwez and Gascuel, the developers of one of the best quartet methods, conjecture that quartet-based methods have inherent limitations that make them unable to produce trees as accurate as neighbor joining or maximum parsimony. In this paper, we present Short Quartet Puzzling, a new quartet-based phylogeny reconstruction algorithm, and we demonstrate the improved topological accuracy of the new method over maximum parsimony and neighbor joining, disproving the conjecture of Ranwez and Gascuel. We also show a dramatic improvement over Quartet Puzzling. Thus, while our new method is not compared to any ML method (as it is not expected to be as accurate as the best of these), this study shows that quartet methods are not as limited in performance as was previously conjectured, and opens the possibility to further improvements through new algorithmic designs.

AB - Quartet-based phylogeny reconstruction methods, such as Quartet Puzzling, were introduced in the hope that they might be competitive with maximum likelihood methods, without being as computationally intensive. However, despite the numerous quartet-based methods that have been developed, their performance in simulation has been disappointing. In particular, Ranwez and Gascuel, the developers of one of the best quartet methods, conjecture that quartet-based methods have inherent limitations that make them unable to produce trees as accurate as neighbor joining or maximum parsimony. In this paper, we present Short Quartet Puzzling, a new quartet-based phylogeny reconstruction algorithm, and we demonstrate the improved topological accuracy of the new method over maximum parsimony and neighbor joining, disproving the conjecture of Ranwez and Gascuel. We also show a dramatic improvement over Quartet Puzzling. Thus, while our new method is not compared to any ML method (as it is not expected to be as accurate as the best of these), this study shows that quartet methods are not as limited in performance as was previously conjectured, and opens the possibility to further improvements through new algorithmic designs.

KW - Algorithms

KW - Biology

KW - Computational molecular biology

KW - Evolution

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

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

U2 - 10.1089/cmb.2007.0103

DO - 10.1089/cmb.2007.0103

M3 - Article

C2 - 18199023

AN - SCOPUS:39449105691

VL - 15

SP - 91

EP - 103

JO - Journal of Computational Biology

JF - Journal of Computational Biology

SN - 1066-5277

IS - 1

ER -