Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

A phase transition for a random cluster model on phylogenetic trees.

Elchanan Mossel1, Mike Steel

  • 1Computer Science and Statistics, University of California, Berkeley, CA, USA. mossel@stat.berkeley.edu

Mathematical Biosciences
|January 24, 2004
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Counting Rankings of Tree-Child Networks.

Bulletin of mathematical biology·2026
Same author

Predicting the depth of the most recent common ancestor of a random sample of k species: the impact of phylogenetic tree shape.

Journal of mathematical biology·2026
Same author

A Dichotomy Law for Certain Classes of Phylogenetic Networks.

Bulletin of mathematical biology·2025
Same author

The Asymptotic Distribution of the <i>k</i>-Robinson-Foulds Dissimilarity Measure on Labeled Trees.

Journal of computational biology : a journal of computational molecular cell biology·2025
Same author

Surprising effects of differential loss in genome evolution: the last-one-out.

FEMS microbiology letters·2025
Same author

Asymptotic Enumeration of Normal and Hybridization Networks via Tree Decoration.

Bulletin of mathematical biology·2025

We developed a model for genomic evolution and found that the number of samples needed to reconstruct a tree transitions from logarithmic to polynomial with mutation rate. A polynomial-time algorithm works for the logarithmic region.

Area of Science:

  • Computational Biology
  • Evolutionary Biology
  • Phylogenetics

Background:

  • Genomic evolution can be modeled using Markov processes.
  • Reconstructing evolutionary trees from data is a fundamental problem.

Purpose of the Study:

  • To investigate a simple model for generating random partitions of a tree's leaf set.
  • To determine the number of samples (k) required for accurate tree reconstruction.
  • To explore the relationship between mutation rate and the required sample size.

Main Methods:

  • Developed a simple model for random tree partitions.
  • Analyzed the tree reconstruction problem based on independent samples.
  • Identified a phase transition in the required sample size k.
  • Described a polynomial-time tree reconstruction algorithm.

Related Experiment Videos

Main Results:

  • Demonstrated a phase transition for k, showing dependence on mutation rate.
  • Observed a shift from logarithmic to polynomial dependence of k on tree size.
  • Presented a polynomial-time algorithm effective in the logarithmic region.

Conclusions:

  • The number of samples needed for tree reconstruction is sensitive to mutation rates.
  • A phase transition exists, impacting the feasibility of reconstruction.
  • Efficient algorithms can reconstruct trees when sample requirements are logarithmic.