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

Efficient parsimony-based methods for phylogenetic network reconstruction.

Guohua Jin1, Luay Nakhleh, Sagi Snir

  • 1Department of Computer Science, Rice University, Houston, TX, USA.

Bioinformatics (Oxford, England)
|January 24, 2007
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

YTHDF1-modified neural stem cells confer neuroprotection and promote functional recovery following traumatic brain injury.

Brain research bulletin·2026
Same author

Impact of Data Error on Phylogenetic Network Inference from Gene Trees Under the Multispecies Network Coalescent.

Methods in molecular biology (Clifton, N.J.)·2026
Same author

Leveraging spectrum of graph sheaf Laplacian as a genome-architecture-aware measure of microbiome diversity.

bioRxiv : the preprint server for biology·2026
Same author

Development and validation of a novel scoring scale for colonic endocytoscopy staining quality.

Scientific reports·2026
Same author

Design of bacterial DNT sensors based on computational models.

Nucleic acids research·2026
Same author

Designing genetically stable multicopy gene constructs with the ChimeraUGEM web server.

NAR genomics and bioinformatics·2025
Same journal

3DICE: Interpretable 3D Cross-Modal Learning for Drug-Target Interaction Prediction and Large-Scale Drug Discovery.

Bioinformatics (Oxford, England)·2026
Same journal

KASSPer: Kinase Active Site Structure Prediction using Protein and Ligand Language Models and Its Application to Virtual Screening.

Bioinformatics (Oxford, England)·2026
Same journal

IDR searcher: a search engine solution for public image resources.

Bioinformatics (Oxford, England)·2026
Same journal

KCFtools: Rapid alignment-free method for introgression screening and GWAS using k-mer profiles.

Bioinformatics (Oxford, England)·2026
Same journal

Meta2DB: Curated shotgun metagenomic feature sets and metadata for health state prediction.

Bioinformatics (Oxford, England)·2026
Same journal

conMItion: an R package adjusting confounding factors for associations in multi-omics.

Bioinformatics (Oxford, England)·2026
See all related articles

Phylogenetic network reconstruction using maximum parsimony is computationally challenging. This study introduces an NP-hard proof and efficient algorithms for inferring evolutionary histories beyond simple trees, including horizontal gene transfer (HGT).

Area of Science:

  • Evolutionary Biology
  • Bioinformatics
  • Computational Biology

Background:

  • Phylogenies represent evolutionary histories, typically as trees.
  • Complex evolutionary events like hybrid speciation and horizontal gene transfer (HGT) necessitate phylogenetic networks.
  • Maximum parsimony is a common criterion for phylogenetic inference, aiming to minimize evolutionary change.

Purpose of the Study:

  • To address the computational challenges of applying maximum parsimony to phylogenetic networks.
  • To develop efficient algorithms for phylogenetic network reconstruction and HGT detection.
  • To provide theoretical analysis and practical testing of parsimony-based network inference.

Main Methods:

  • Proved the NP-hardness of scoring phylogenetic networks using maximum parsimony.

Related Experiment Videos

  • Developed an improved fixed-parameter tractable algorithm for phylogenetic network scoring.
  • Devised efficient heuristics for parsimony-based phylogenetic network reconstruction.

    • Main Results:

    • The computational problem of phylogenetic network parsimony scoring is NP-hard.
    • An efficient fixed-parameter tractable algorithm was developed.
    • Heuristics demonstrated promising results on synthetic and biological data (rbcL gene).

    Conclusions:

    • Maximum parsimony can be applied to infer complex evolutionary histories represented by networks.
    • The developed algorithms offer computational improvements for phylogenetic network reconstruction.
    • The methods show potential for analyzing biological data, including HGT events in bacteria.