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

Improved parameterized complexity of the maximum agreement subtree and maximum compatible tree problems.

Vincent Berry1, François Nicolas

  • 1Equipe Méthodes et Algorithmes pour la Bioinformatique-L.I.R.M.M., Montpellier, France. vberry@lirmm.fr

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 Deep Learning Algorithm for Liver Metastasis Detection at Contrast-enhanced Abdominal CT in Patients with Colorectal Cancer: A Comparative Study with Radiologists.

Radiology. Imaging cancer·2026
Same author

Abel inversion from central-projection background oriented schlieren observations for reconstruction of axisymmetric refractive media.

Applied optics·2025
Same author

Insights into the evolution, virulence and speciation of <i>Babesia MO1</i> and <i>Babesia divergens</i> through multiomics analyses.

Emerging microbes & infections·2024
Same author

Multiomics analysis reveals <i>B.</i> MO1 as a distinct <i>Babesia</i> species and provides insights into its evolution and virulence.

bioRxiv : the preprint server for biology·2024
Same author

Using gamification to improve engagement and learning outcomes in medical microbiology: the case study of 'BacteriaGame'.

FEMS microbiology letters·2023
Same author

Phase transition and thermal stability of epitaxial PtSe<sub>2</sub> nanolayer on Pt(111).

RSC advances·2022
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

This study introduces efficient algorithms for the Maximum Agreement Subtree (MAST) and Maximum Compatible Tree (MCT) problems in phylogenetics. These algorithms improve computational tractability for analyzing evolutionary relationships across different datasets.

Area of Science:

  • Computational Phylogenetics
  • Evolutionary Biology
  • Algorithm Design

Background:

  • Phylogenetic trees are crucial for understanding evolutionary relationships.
  • Comparing multiple phylogenetic trees presents computational challenges.
  • Existing methods for Maximum Agreement Subtree (MAST) and Maximum Compatible Tree (MCT) problems have limitations.

Purpose of the Study:

  • To develop efficient algorithms for solving the MAST and MCT problems.
  • To enhance the analysis of evolutionary tree consensus and compatibility.
  • To provide a framework for inferring supertrees and identifying gene transfer events.

Main Methods:

  • Developed two linear-time algorithms for checking tree isomorphism and compatibility.
  • Utilized these algorithms as subroutines to solve MAST and MCT.

Related Experiment Videos

  • Designed exact fixed-parameter tractable algorithms for rooted and unrooted trees.

    • Main Results:

    • Achieved linear time complexity for tree isomorphism and compatibility checks.
    • Provided fixed-parameter tractable algorithms for MAST and MCT.
    • Demonstrated improved performance for MAST and established tractability for MCT.

    Conclusions:

    • The developed algorithms offer significant advancements in solving MAST and MCT problems.
    • These methods enhance the computational feasibility of phylogenetic analysis.
    • The findings contribute to more robust inference of evolutionary histories and supertrees.