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

Reconciliation with non-binary species trees.

B Vernot1, M Stolzer, A Goldman

  • 1Departments of Biological Sciences and Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, USA. durand@cs.cmu.edu.

Computational Systems Bioinformatics. Computational Systems Bioinformatics Conference
|October 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

A novel approach to cervical dilation for second-trimester dilation and evacuation in a myomatous uterus.

Contraception·2025
Same author

Evaluating the prospective utility of pharmacogenetics reporting among Canadian Armed Forces personnel receiving pharmacotherapy: a preliminary assessment towards precision psychiatric care.

BMJ military health·2023
Same author

A phase II open-label trial of avelumab plus axitinib in previously treated non-small-cell lung cancer or treatment-naïve, cisplatin-ineligible urothelial cancer.

ESMO open·2023
Same author

Developing a platform for Fresnel diffractive radiography with 1 μm spatial resolution at the National Ignition Facility.

The Review of scientific instruments·2023
Same author

UPPER ARM CONTOURING - A NARRATIVE REVIEW.

Georgian medical news·2023
Same author

PIGMENTED NODULAR CYSTIC HIDRADENOMA OF THE ANKLE.

Georgian medical news·2021
Same journal

Novel Gene Discovery in the Human Malaria Parasite using Nucleosome Positioning Data.

Computational systems bioinformatics. Computational Systems Bioinformatics Conference·2014
Same journal

Proceedings of Computational Systems Bioinformatics 2008. August 26-29, 2008. Palo Alto, California, USA.

Computational systems bioinformatics. Computational Systems Bioinformatics Conference·2009
Same journal

Graph wavelet alignment kernels for drug virtual screening.

Computational systems bioinformatics. Computational Systems Bioinformatics Conference·2009
Same journal

Fast multisegment alignments for temporal expression profiles.

Computational systems bioinformatics. Computational Systems Bioinformatics Conference·2009
Same journal

Knowledge representation and data mining for biological imaging.

Computational systems bioinformatics. Computational Systems Bioinformatics Conference·2009
Same journal

Efficient haplotype inference from pedigrees with missing data using linear systems with disjoint-set data structures.

Computational systems bioinformatics. Computational Systems Bioinformatics Conference·2009
See all related articles

Resolving gene and species tree conflicts is crucial. This study introduces the first algorithm for reconciling binary gene trees with non-binary species trees, accurately inferring gene duplication and loss events.

Area of Science:

  • Computational Biology
  • Phylogenetics
  • Bioinformatics

Background:

  • Gene and species tree reconciliation addresses topological incongruence using gene duplication and loss events.
  • Existing methods struggle with non-binary species trees, overestimating duplications by conflating them with deep coalescence.
  • Non-binary species trees are common, with 64% of NCBI taxonomy branch points having multiple children.

Purpose of the Study:

  • To present the first formal algorithm for reconciling binary gene trees with non-binary species trees under a duplication-loss parsimony model.
  • To accurately infer the minimum number of gene duplications and losses, distinguishing them from deep coalescence.
  • To implement these algorithms in a user-friendly and high-throughput software.

Main Methods:

Related Experiment Videos

  • Developed a novel algorithm for reconciling binary gene trees with non-binary species trees.
  • Utilized a space-efficient mapping between gene and species trees.
  • Achieved a time complexity of O(|V(G)| . (k(S) + h(S))) for inferring duplications and losses.
  • Introduced a dynamic programming algorithm for a combined loss model.

    • Main Results:

    • The algorithm accurately infers the minimum number of duplications and losses when reconciling gene trees with non-binary species trees.
    • The computational efficiency is dependent on the gene tree size and species tree width and height.
    • A combined loss model was developed to account for losses in sibling species.

    Conclusions:

    • This work provides the first accurate method for reconciling gene trees with non-binary species trees.
    • The developed algorithms are implemented in the NOTUNG software, supporting both interactive and automated analyses.
    • Accurate reconciliation is vital for downstream biological applications like ortholog identification and evolutionary analysis.