On the Inference of Large Phylogenies with Long Branches

How Long Is Too Long?

Elchanan Mossel, Sébastien Roch, Allan M. Sly

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

The accurate reconstruction of phylogenies from short molecular sequences is an important problem in computational biology. Recent work has highlighted deep connections between sequence-length requirements for high-probability phylogeny reconstruction and the related problem of the estimation of ancestral sequences. In Daskalakis et al. (in Probab. Theory Relat. Fields 2010), building on the work of Mossel (Trans. Am. Math. Soc. 356(6):2379-2404, 2004), a tight sequence-length requirement was obtained for the simple CFN model of substitution, that is, the case of a two-state symmetric rate matrix Q. In particular the required sequence length for high-probability reconstruction was shown to undergo a sharp transition (from O(log n) to poly(n), where n is the number of leaves) at the "critical" branch length g ML(Q) (if it exists) of the ancestral reconstruction problem defined roughly as follows: below g ML(Q) the sequence at the root can be accurately estimated from sequences at the leaves on deep trees, whereas above g ML(Q) information decays exponentially quickly down the tree. Here, we consider a more general evolutionary model, the GTR model, where the q × q rate matrix Q is reversible with q ≥ 2. For this model, recent results of Roch (Preprint, 2009) show that the tree can be accurately reconstructed with sequences of length O(log(n)) when the branch lengths are below g Lin(Q), known as the Kesten-Stigum (KS) bound, up to which ancestral sequences can be accurately estimated using simple linear estimators. Although for the CFN model g ML(Q)=g Lin(Q) (in other words, linear ancestral estimators are in some sense best possible), it is known that for the more general GTR models one has g ML(Q) ≥ g Lin(Q) with a strict inequality in many cases. Here, we show that this phenomenon also holds for phylogenetic reconstruction by exhibiting a family of symmetric models Q and a phylogenetic reconstruction algorithm which recovers the tree from O(log n)-length sequences for some branch lengths in the range (g Lin(Q), g ML(Q)). Second, we prove that phylogenetic reconstruction under GTR models requires a polynomial sequence-length for branch lengths above g ML(Q).

Original languageEnglish (US)
Pages (from-to)1627-1644
Number of pages18
JournalBulletin of Mathematical Biology
Volume73
Issue number7
DOIs
StatePublished - Jul 1 2011

Fingerprint

Phylogeny
phylogeny
Branch
Phylogenetics
Computational Biology
phylogenetics
Q-matrix
Linear Estimator
Model
matrix
Leaves
Requirements
substitution
Substitution reactions
Reconstruction Algorithm
bioinformatics
Polynomials
leaves
Substitution
deterioration

All Science Journal Classification (ASJC) codes

  • Agricultural and Biological Sciences(all)
  • Environmental Science(all)
  • Mathematics(all)
  • Biochemistry, Genetics and Molecular Biology(all)
  • Neuroscience(all)
  • Pharmacology
  • Computational Theory and Mathematics
  • Immunology

Cite this

@article{e7d333677ec54162ac8cf7369f857f5d,
title = "On the Inference of Large Phylogenies with Long Branches: How Long Is Too Long?",
abstract = "The accurate reconstruction of phylogenies from short molecular sequences is an important problem in computational biology. Recent work has highlighted deep connections between sequence-length requirements for high-probability phylogeny reconstruction and the related problem of the estimation of ancestral sequences. In Daskalakis et al. (in Probab. Theory Relat. Fields 2010), building on the work of Mossel (Trans. Am. Math. Soc. 356(6):2379-2404, 2004), a tight sequence-length requirement was obtained for the simple CFN model of substitution, that is, the case of a two-state symmetric rate matrix Q. In particular the required sequence length for high-probability reconstruction was shown to undergo a sharp transition (from O(log n) to poly(n), where n is the number of leaves) at the {"}critical{"} branch length g ML(Q) (if it exists) of the ancestral reconstruction problem defined roughly as follows: below g ML(Q) the sequence at the root can be accurately estimated from sequences at the leaves on deep trees, whereas above g ML(Q) information decays exponentially quickly down the tree. Here, we consider a more general evolutionary model, the GTR model, where the q × q rate matrix Q is reversible with q ≥ 2. For this model, recent results of Roch (Preprint, 2009) show that the tree can be accurately reconstructed with sequences of length O(log(n)) when the branch lengths are below g Lin(Q), known as the Kesten-Stigum (KS) bound, up to which ancestral sequences can be accurately estimated using simple linear estimators. Although for the CFN model g ML(Q)=g Lin(Q) (in other words, linear ancestral estimators are in some sense best possible), it is known that for the more general GTR models one has g ML(Q) ≥ g Lin(Q) with a strict inequality in many cases. Here, we show that this phenomenon also holds for phylogenetic reconstruction by exhibiting a family of symmetric models Q and a phylogenetic reconstruction algorithm which recovers the tree from O(log n)-length sequences for some branch lengths in the range (g Lin(Q), g ML(Q)). Second, we prove that phylogenetic reconstruction under GTR models requires a polynomial sequence-length for branch lengths above g ML(Q).",
author = "Elchanan Mossel and S{\'e}bastien Roch and Sly, {Allan M.}",
year = "2011",
month = "7",
day = "1",
doi = "https://doi.org/10.1007/s11538-010-9584-6",
language = "English (US)",
volume = "73",
pages = "1627--1644",
journal = "Bulletin of Mathematical Biology",
issn = "0092-8240",
publisher = "Springer New York",
number = "7",

}

On the Inference of Large Phylogenies with Long Branches : How Long Is Too Long? / Mossel, Elchanan; Roch, Sébastien; Sly, Allan M.

In: Bulletin of Mathematical Biology, Vol. 73, No. 7, 01.07.2011, p. 1627-1644.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the Inference of Large Phylogenies with Long Branches

T2 - How Long Is Too Long?

AU - Mossel, Elchanan

AU - Roch, Sébastien

AU - Sly, Allan M.

PY - 2011/7/1

Y1 - 2011/7/1

N2 - The accurate reconstruction of phylogenies from short molecular sequences is an important problem in computational biology. Recent work has highlighted deep connections between sequence-length requirements for high-probability phylogeny reconstruction and the related problem of the estimation of ancestral sequences. In Daskalakis et al. (in Probab. Theory Relat. Fields 2010), building on the work of Mossel (Trans. Am. Math. Soc. 356(6):2379-2404, 2004), a tight sequence-length requirement was obtained for the simple CFN model of substitution, that is, the case of a two-state symmetric rate matrix Q. In particular the required sequence length for high-probability reconstruction was shown to undergo a sharp transition (from O(log n) to poly(n), where n is the number of leaves) at the "critical" branch length g ML(Q) (if it exists) of the ancestral reconstruction problem defined roughly as follows: below g ML(Q) the sequence at the root can be accurately estimated from sequences at the leaves on deep trees, whereas above g ML(Q) information decays exponentially quickly down the tree. Here, we consider a more general evolutionary model, the GTR model, where the q × q rate matrix Q is reversible with q ≥ 2. For this model, recent results of Roch (Preprint, 2009) show that the tree can be accurately reconstructed with sequences of length O(log(n)) when the branch lengths are below g Lin(Q), known as the Kesten-Stigum (KS) bound, up to which ancestral sequences can be accurately estimated using simple linear estimators. Although for the CFN model g ML(Q)=g Lin(Q) (in other words, linear ancestral estimators are in some sense best possible), it is known that for the more general GTR models one has g ML(Q) ≥ g Lin(Q) with a strict inequality in many cases. Here, we show that this phenomenon also holds for phylogenetic reconstruction by exhibiting a family of symmetric models Q and a phylogenetic reconstruction algorithm which recovers the tree from O(log n)-length sequences for some branch lengths in the range (g Lin(Q), g ML(Q)). Second, we prove that phylogenetic reconstruction under GTR models requires a polynomial sequence-length for branch lengths above g ML(Q).

AB - The accurate reconstruction of phylogenies from short molecular sequences is an important problem in computational biology. Recent work has highlighted deep connections between sequence-length requirements for high-probability phylogeny reconstruction and the related problem of the estimation of ancestral sequences. In Daskalakis et al. (in Probab. Theory Relat. Fields 2010), building on the work of Mossel (Trans. Am. Math. Soc. 356(6):2379-2404, 2004), a tight sequence-length requirement was obtained for the simple CFN model of substitution, that is, the case of a two-state symmetric rate matrix Q. In particular the required sequence length for high-probability reconstruction was shown to undergo a sharp transition (from O(log n) to poly(n), where n is the number of leaves) at the "critical" branch length g ML(Q) (if it exists) of the ancestral reconstruction problem defined roughly as follows: below g ML(Q) the sequence at the root can be accurately estimated from sequences at the leaves on deep trees, whereas above g ML(Q) information decays exponentially quickly down the tree. Here, we consider a more general evolutionary model, the GTR model, where the q × q rate matrix Q is reversible with q ≥ 2. For this model, recent results of Roch (Preprint, 2009) show that the tree can be accurately reconstructed with sequences of length O(log(n)) when the branch lengths are below g Lin(Q), known as the Kesten-Stigum (KS) bound, up to which ancestral sequences can be accurately estimated using simple linear estimators. Although for the CFN model g ML(Q)=g Lin(Q) (in other words, linear ancestral estimators are in some sense best possible), it is known that for the more general GTR models one has g ML(Q) ≥ g Lin(Q) with a strict inequality in many cases. Here, we show that this phenomenon also holds for phylogenetic reconstruction by exhibiting a family of symmetric models Q and a phylogenetic reconstruction algorithm which recovers the tree from O(log n)-length sequences for some branch lengths in the range (g Lin(Q), g ML(Q)). Second, we prove that phylogenetic reconstruction under GTR models requires a polynomial sequence-length for branch lengths above g ML(Q).

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

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

U2 - https://doi.org/10.1007/s11538-010-9584-6

DO - https://doi.org/10.1007/s11538-010-9584-6

M3 - Article

VL - 73

SP - 1627

EP - 1644

JO - Bulletin of Mathematical Biology

JF - Bulletin of Mathematical Biology

SN - 0092-8240

IS - 7

ER -