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

Minimum-flip supertrees: complexity and algorithms.

Duhong Chen1, Oliver Eulenstein, David Fernandez-Baca

  • 1Department of Computer Science, Iowa State University, Ames, IA 50011-1040, USA. jackie@iastate.edu

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

A PLUM Job: Peptide modeLs for Understanding and engineering antiMicrobial therapeutics.

bioRxiv : the preprint server for biology·2026
Same author

Phylo-rs: an extensible phylogenetic analysis library in rust.

BMC bioinformatics·2025
Same author

Computing generalized cophenetic distances under all Lp norms: A near-linear time algorithmic framework.

PLoS computational biology·2025
Same author

Discovering genomic islands in unannotated bacterial genomes using sequence embedding.

Bioinformatics advances·2024
Same author

Asymmetric Cluster-Based Measures for Comparative Phylogenetics.

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

Selective trace elements significantly enhanced methane production in coal bed methane systems by stimulating microbial activity.

Microbiology spectrum·2024
Same journal

circ2DGNN: circRNA-Disease Association Prediction via Transformer-Based Graph Neural Network.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Hierarchical Hypergraph Learning in Association- Weighted Heterogeneous Network for miRNA- Disease Association Identification.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Discriminative Domain Adaption Network for Simultaneously Removing Batch Effects and Annotating Cell Types in Single-Cell RNA-Seq.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

MLW-BFECF: A Multi-Weighted Dynamic Cascade Forest Based on Bilinear Feature Extraction for Predicting the Stage of Kidney Renal Clear Cell Carcinoma on Multi-Modal Gene Data.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

An End-to-End Knowledge Graph Fused Graph Neural Network for Accurate Protein-Protein Interactions Prediction.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Generative Biomedical Event Extraction With Constrained Decoding Strategy.

IEEE/ACM transactions on computational biology and bioinformatics·2024
See all related articles

Resolving inconsistencies in phylogenetic supertree construction is challenging. This study introduces a minimum-flip approach to reconcile conflicting evolutionary trees, proving its NP-completeness but also its tractability for specific cases.

Area of Science:

  • Computational Biology
  • Phylogenetics
  • Algorithm Design

Background:

  • Supertree problems involve combining multiple phylogenetic trees.
  • Inconsistencies in input trees complicate supertree construction.
  • Phylogenetic trees can be represented by their exhibited clusters.

Purpose of the Study:

  • To address inconsistencies in rooted phylogenetic supertree construction.
  • To define and analyze the minimum-flip problem for resolving tree conflicts.
  • To investigate the computational complexity and develop algorithms for the minimum-flip problem.

Main Methods:

  • Representing rooted phylogenetic trees by their clusters.
  • Defining a 'flip' operation as moving a taxon within a cluster hierarchy.

Related Experiment Videos

  • Proving NP-completeness for the minimum-flip problem.
  • Demonstrating fixed-parameter tractability.
  • Developing approximation algorithms for special cases.

    • Main Results:

    • The minimum-flip problem for resolving supertree inconsistencies is NP-complete.
    • The problem is shown to be fixed-parameter tractable.
    • Approximation algorithms are provided for specific scenarios.

    Conclusions:

    • The minimum-flip problem is a computationally hard but tractable problem in phylogenetics.
    • The developed algorithms offer practical approaches for reconciling conflicting phylogenetic data.
    • This work contributes to robust methods for evolutionary tree reconstruction.