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

Using max cut to enhance rooted trees consistency.

Sagi Snir1, Satish Rao

  • 1Department of Mathematics, University of California, Berkeley, CA 94720, USA. ssagi@math.berkeley.edu

IEEE/ACM Transactions on Computational Biology and Bioinformatics
|November 7, 2006
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

The prevalence and incidence of narcolepsy in the United States: a real-world observational study using a validated narcolepsy case definition.

Sleep advances : a journal of the Sleep Research Society·2026
Same author

Clinical and quality of life consequences of regimen switching delays in HIV management: a stratified cohort analysis.

Scientific reports·2025
Same author

A graph homomorphism approach for unraveling histories of metastatic cancers and viral outbreaks under evolutionary constraints.

Nature communications·2025
Same author

Evolution of gene order in prokaryotes is driven primarily by gene gain and loss.

bioRxiv : the preprint server for biology·2025
Same author

Evolution of gene order in prokaryotes is driven primarily by gene gain and loss.

Proceedings of the National Academy of Sciences of the United States of America·2025
Same author

Early Increase in Serum Transthyretin by Acoramidis Independently Predicts Improved Survival in TTR Amyloid Cardiomyopathy.

Journal of the American College of Cardiology·2025

Supertree methods construct large phylogenetic trees from smaller ones. This study introduces a novel heuristic approach that significantly outperforms existing methods for building evolutionary trees, especially when dealing with conflicting data.

Area of Science:

  • Phylogenetics
  • Computational Biology
  • Evolutionary Biology

Background:

  • Supertree methods are essential for constructing large phylogenetic trees, particularly the tree of life, due to limitations in accurate reconstruction methods for numerous taxa.
  • Existing supertree methods face computational challenges, with NP-complete and NP-hard problems arising from quartet and triplet inconsistencies, respectively.

Purpose of the Study:

  • To develop a novel heuristic supertree method that addresses the NP-hard problem of finding a tree that maximizes agreement with input rooted triplets.
  • To provide a method that guarantees properties of current approaches while offering superior performance.

Main Methods:

  • The study proposes a new heuristic approach based on a divide and conquer strategy.
  • It replaces the min cut in the divide step with a max cut on a modified graph representation of triplet inconsistencies.

Related Experiment Videos

  • A lightweight semidefinite programming-like heuristic is employed for efficient computation.

    • Main Results:

    • The novel heuristic method guarantees the required properties of existing supertree algorithms.
    • Experimental results demonstrate significant performance improvements over current state-of-the-art methods.
    • The approach achieves very fast running times due to its efficient heuristic.

    Conclusions:

    • The presented supertree heuristic offers a more effective and efficient solution for constructing large phylogenetic trees.
    • This method advances the field of computational phylogenetics by providing a robust tool for inferring evolutionary relationships from complex datasets.