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

Column sorting: rapid calculation of the phylogenetic likelihood function.

Sergei L Kosakovsky Pond1, Spencer V Muse

  • 1Department of Mathematics, University of Arizona, Tucson, Arizona 85271, USA.

Systematic Biology
|November 17, 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

Beyond Invariable Sites: Using Evolutionary Stasis to Map Multi-Layered Constraints on the Evolution of Viral and Mammalian Genomes.

bioRxiv : the preprint server for biology·2026
Same author

Characterizing Physicochemical Selection in Protein Evolution with Property-Informed Models (PRIME).

bioRxiv : the preprint server for biology·2026
Same author

CAPHEINE, or everything and the kitchen sink: a workflow for automating selection analyses using HyPhy.

bioRxiv : the preprint server for biology·2026
Same author

Dynamics of natural selection preceding human viral epidemics and pandemics.

Cell·2026
Same author

MoleRate: comparing molecular relative evolutionary rates to detect convergent evolution.

Evolution; international journal of organic evolution·2025
Same author

Defective HIV DNA genomes provide ancestral relevance critical for phylogenetic inference of reservoir dynamics.

bioRxiv : the preprint server for biology·2025

This study introduces a graph theory algorithm to optimize likelihood calculations in molecular evolution. The method significantly speeds up phylogenetic analyses by exploiting data structure, enabling larger datasets and deeper tree searches.

Area of Science:

  • Computational Biology
  • Molecular Evolution
  • Phylogenetics

Background:

  • Likelihood methods are central to molecular evolutionary analyses.
  • Felsenstein's pruning algorithm enables feasible likelihood calculations.
  • Computational efficiency can be improved by exploiting data structure.

Purpose of the Study:

  • To develop an algorithm for computational reduction in likelihood calculations.
  • To exploit repetitive structures in alignment data for faster analyses.
  • To enhance the scalability of phylogenetic methods.

Main Methods:

  • Developed a novel algorithm using graph theory.
  • Identified and exploited identical components in likelihood calculations for similar alignment columns.

Related Experiment Videos

  • Implemented an optimal ordering for evaluating alignment columns.

    • Main Results:

    • Achieved typical computational savings of 15%-50%.
    • Observed real-data time reductions up to 80%.
    • Algorithm overhead is minimal and recovered on most datasets.

    Conclusions:

    • The new algorithm significantly accelerates likelihood-based phylogenetic analyses.
    • Faster computations allow for the analysis of larger datasets.
    • Enables more extensive searches of tree topology space in evolutionary studies.