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

Algorithms for multiple genome rearrangement by signed reversals.

Shiquan Wu1, Xun Gu

  • 1Center of Bioinformatics and Biological Statistics, Iowa State University, Ames, IA 50011, USA. sqwu@cs.iastate.edu

Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing
|February 27, 2003
PubMed
Summary

This study addresses the NP-hard multiple genome rearrangement problem using signed reversals. Two novel algorithms, a polynomial-time approximation and an exact exponential-time algorithm, efficiently find optimal Steiner nodes for genome reconstruction.

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

Cross-species integration of single-cell data reveals conserved pathology-associated cell populations across animal models and human samples.

Cell reports methods·2026
Same author

Characterization of Cancer Hallmark Enhancer RNA Uncovers Novel Strategies for Precision Oncology.

Genomics, proteomics & bioinformatics·2026
Same author

MRDviz: an integrated platform for interactive visualization and joint simulation of minimal residual disease trajectories and associated survival outcomes.

Bioinformatics advances·2026
Same author

Oxygen-sparing photodynamic therapy via dissolving microneedles for rheumatoid arthritis.

International journal of pharmaceutics: X·2026
Same author

ProtFPreDTI: Drug-Target Interaction Prediction Study and LIME Interpretability Analysis Based on the ProtBERT Deep Language Model with Adaptive Fuzzy Sampling Strategy.

Bioconjugate chemistry·2026
Same author

Identification of cancer mini-drivers by deciphering selective landscape in the cancer genome.

Briefings in bioinformatics·2026

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Genomics

Background:

  • The multiple genome rearrangement problem seeks to reconstruct ancestral genomes from extant ones.
  • Signed reversals are a key operation in genome evolution and reconstruction.

Purpose of the Study:

  • To develop efficient algorithms for the NP-hard multiple genome rearrangement problem.
  • To find the minimum number of signed reversals required to transform a collection of genomes.

Main Methods:

  • Designed a polynomial-time approximation algorithm (Neighbor-perturbing) for finding near-optimal Steiner nodes.
  • Developed an exact exponential-time algorithm (branch-and-bound) for the median problem to find optimal Steiner nodes.
  • Implemented both algorithms and compared their efficiency experimentally.

Related Experiment Videos

Main Results:

  • The Neighbor-perturbing algorithm provides an efficient approximation for large-scale problems.
  • The branch-and-bound algorithm guarantees optimality for the median problem.
  • Experimental results demonstrate superior efficiency compared to existing methods like GRAPPA, BPAnalysis, and MGR.

Conclusions:

  • The developed algorithms offer significant improvements in efficiency and accuracy for the multiple genome rearrangement problem.
  • These methods provide valuable tools for comparative genomics and evolutionary studies.
  • The study highlights the effectiveness of Steiner tree approaches in genome reconstruction.