MétaCan
Menu
Back to cohort
Record W2128020980 · doi:10.1145/1132516.1132540

Optimal phylogenetic reconstruction

2006· article· en· W2128020980 on OpenAlex

Why this work is in the frame

A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.

fundA Canadian funder is recorded on the work.
no affNo Canadian affiliation: this work is invisible to an affiliation-only frame.
No Canadian affiliation. An affiliation-only frame, the usual design, would never have seen this work. It is one of the works that make the case for inverting the frame.

Bibliographic record

Venuenot available
Typearticle
Languageen
FieldComputer Science
TopicAlgorithms and Data Compression
Canadian institutionsnot available
FundersNatural Sciences and Engineering Research Council of CanadaHarvard UniversityNational Science Foundation
KeywordsTree (set theory)Phylogenetic treeMarkov chainMathematicsCombinatoricsAlgorithmTree rearrangementSequence (biology)Discrete mathematicsBiologyStatisticsGenetics

Abstract

fetched live from OpenAlex

One of the major tasks of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on the true evolutionary tree. Given samples from this Markov chain at the leaves of the tree, the goal is to reconstruct the evolutionary tree.It is well known that in order to reconstruct a tree on n leaves, sequences of length Ω(log n) are needed. It was conjectured by M. Steel that for the CFN evolutionary model, if the mutation probability on all edges of the tree is less than p* = (√2-1)/23/2, then the tree can be recovered from sequences of length O(log n). This was proven by the second author in the special case where the tree is "balanced". The second author also proved that if all edges have mutation probability larger than p* then the length needed is nΩ(1). This "phase-transition" in the number of samples needed is closely related to the phase transition for the reconstruction problem (or extremality of free measure) studied extensively in statistical physics, probability and computer science.Here we complete the proof of Steel's conjecture and give a reconstruction algorithm using optimal (up to a multiplicative constant) sequence length. Our results further extend to obtain an optimal reconstruction algorithm for the Jukes-Cantor model with short edges. All reconstruction algorithms run in polynomial time.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.

Full frame distilled prediction

Teacher imitation

Not calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.

metaresearch head score (Codex)0.000
metaresearch head score (Gemma)0.000
Version: codex-gemma-dda1882f352aValidation status: machine_predicted_unvalidated
Candidate categoriesnone
Consensus categoriesnone
DomainCandidate signal: none · Consensus signal: none
Study designCandidate signal: Simulation or modeling · Consensus signal: none
GenreCandidate signal: Methods · Consensus signal: Methods
Teacher disagreement score0.900
Threshold uncertainty score0.142

Codex and Gemma teacher scores by category

CategoryCodexGemma
Metaresearch0.0000.000
Meta-epidemiology (narrow)0.0000.000
Meta-epidemiology (broad)0.0000.000
Bibliometrics0.0000.000
Science and technology studies0.0000.000
Scholarly communication0.0000.000
Open science0.0000.000
Research integrity0.0000.000
Insufficient payload (model declined to judge)0.0000.000

Machine scores (provisional)

The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.

Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.

Opus teacher head0.007
GPT teacher head0.207
Teacher spread0.199 · how far apart the two teachers sit on this one work
Validation statusscore_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it

Quick stats

Citations90
Published2006
Admission routes1
Has abstractyes

Explore more

Same topicAlgorithms and Data CompressionFrench-language works237,207