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

A linear-time algorithm for computing inversion distance between signed permutations with an experimental study.

D A Bader1, B M Moret, M Yan

  • 1Department of Electrical and Computer Engineering, University of New Mexico, Albuquerque, NM 87131-1356, USA. dbader@eece.unm.edu

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|November 6, 2001
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

[Prokaryotic expression of <i>Echinococcus granulosus</i> Polo-like kinase 2 and immunoprotective efficacy of its recombinant protein].

Zhongguo xue xi chong bing fang zhi za zhi = Chinese journal of schistosomiasis control·2026
Same author

The role of stereotactic body radiotherapy in the management of hepatocellular carcinoma with macroscopic vascular invasion: a narrative review.

ESMO gastrointestinal oncology·2026
Same author

Intracranial arterial plaque combined with cerebral small vessel disease magnetic resonance features to assess ischemic stroke.

Clinical radiology·2025
Same author

Antibiotic-Loaded Polymer-Calcium Phosphate Scaffold for Treating Orthopedic Device-Related Infection in a Rabbit Segmental Bone Defect Model.

Journal of biomedical materials research. Part A·2025
Same author

[Prospective randomized controlled trial on 2 940 nm fractional erbium laser combined with fractional micro-plasma radiofrequency in the treatment of facial atrophic acne scars].

Zhonghua shao shang yu chuang mian xiu fu za zhi·2023
Same author

Electropolishing influence on biocompatibility of additively manufactured Ti-Nb-Ta-Zr: in vivo and in vitro.

Journal of materials science. Materials in medicine·2023
Same journal

GMSA: A Graph Matching and Point Cloud Registration-Based Method for Spatial Transcriptomics Data Alignment.

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

Investigations on Multiple Protein Scaffold Filling.

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

Cell Type Prediction for Single-Cell RNA Sequencing Utilizing Unsupervised Domain Adaptation and Semi-Supervised Learning.

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

PPIGAN: Prediction of Protein-Protein Interactions Using Generative Adversarial Networks.

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

Deep Structure-Enhanced Cell Clustering Model for Single-Cell RNA Sequencing Data.

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

Asymmetric Drug-Drug Interaction Prediction Based on Generative Adversarial Networks and Knowledge Graph.

Journal of computational biology : a journal of computational molecular cell biology·2026
See all related articles

A new linear-time algorithm efficiently computes connected components for signed permutation inversion distance. This stack-based method is faster in theory and practice than previous algorithms.

Area of Science:

  • Computational biology
  • Algorithmic bioinformatics
  • Discrete mathematics

Background:

  • The inversion distance between signed permutations is crucial for genome rearrangement analysis.
  • Previous algorithms, like Berman and Hannenhalli's O(nalpha(n)) method, relied on complex structures like Union-Find.
  • The efficiency of computing connected components significantly impacts overall inversion distance calculation.

Purpose of the Study:

  • To develop a more efficient algorithm for computing connected components of the overlap graph for signed permutations.
  • To improve upon the theoretical and practical performance of existing methods for inversion distance computation.
  • To present a simpler, stack-based algorithm for enhanced practical application.

Main Methods:

  • A novel linear-time algorithm utilizing a stack data structure.

Related Experiment Videos

  • Decomposition of the overlap graph into connected components.
  • Identification of specific graph structures like hurdles.

    • Main Results:

    • The new algorithm achieves linear time complexity, outperforming the O(nalpha(n)) approach.
    • Experimental results show a 2-5x speed-up in connected component computation.
    • Overall inversion distance computation is accelerated by a factor of 1.3-2.

    Conclusions:

    • The proposed stack-based algorithm offers a significant improvement in efficiency for calculating inversion distance.
    • Its simplicity enhances practical implementation in computational biology.
    • This advancement contributes to faster and more accurate genome rearrangement analyses.