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

Divide-and-conquer approach for the exemplar breakpoint distance.

C Thach Nguyen1, Y C Tay, Louxin Zhang

  • 1School of Computing, National University of Singapore, 117543, Singapore.

Bioinformatics (Oxford, England)
|February 17, 2005
PubMed
Summary

This study introduces a novel divide-and-conquer method to efficiently calculate the exemplar breakpoint distance in genomes with multiple gene families. This new approach significantly improves computational efficiency for genome rearrangement problems.

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

Mixing Is Dispensable for Optical Density-Based High-Throughput Growth Screening Assay in Fission Yeast.

International journal of molecular sciences·2026
Same author

Exact and Asymptotic Counts of Binary Phylogenetic Networks with a Few Reticulation Events.

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

On the Size of the Neighborhoods of a Word.

IEEE transactions on computational biology and bioinformatics·2025
Same author

DSA-DeepFM: a dual-stage attention-enhanced DeepFM model for predicting anticancer synergistic drug combinations.

Bioinformatics advances·2025
Same author

Simple k-RF Metrics for Comparison of Labeled DAGs.

IEEE transactions on computational biology and bioinformatics·2025
Same author

PhyloFusion-Fast and Easy Fusion of Rooted Phylogenetic Trees into Rooted Phylogenetic Networks.

Systematic biology·2025

Area of Science:

  • Computational Biology
  • Genomics
  • Bioinformatics

Background:

  • Comparing genomes requires gene correspondence for distance metrics like breakpoint and reversal distances.
  • The exemplar distance problem, formulated by Sankoff, addresses genome comparison with paralogous genes but is NP-hard.
  • Existing methods struggle with the computational complexity of these problems.

Purpose of the Study:

  • To develop a more efficient method for calculating the exemplar breakpoint distance between genomes with multiple gene families.
  • To provide a practical computational tool for genome rearrangement analysis.

Main Methods:

  • A divide-and-conquer algorithm was developed for exemplar breakpoint distance calculation.
  • The approach was combined with Sankoff's branch-and-bound technique.

Related Experiment Videos

  • The method was tested using both simulated and real genomic datasets.

    • Main Results:

    • The proposed divide-and-conquer approach, when combined with branch-and-bound, yields a practical program.
    • The new program demonstrates significantly higher efficiency compared to existing branch-and-bound-only methods.
    • Performance was validated on diverse datasets.

    Conclusions:

    • The developed method offers a substantial improvement in efficiency for calculating exemplar breakpoint distances.
    • This work provides a valuable tool for comparative genomics and understanding genome evolution.
    • The program is available for use by researchers.