Search research articles

ABOUT JoVE

Overview Leadership Blog JoVE Help Center

AUTHORS

Publishing Process Editorial Board Scope & Policies Peer Review FAQ Submit

LIBRARIANS

Testimonials Subscriptions Access Resources Library Advisory Board FAQ

RESEARCH

JoVE Journal Methods Collections JoVE Encyclopedia of Experiments Archive

EDUCATION

JoVE Core JoVE Business JoVE Science Education JoVE Lab Manual Faculty Resource Center Faculty Site

Terms & Conditions of Use

Search research articles

Related Experiment Videos

A (1.5 + epsilon)-approximation algorithm for unsigned translocation distance.

Yun Cui¹, Lusheng Wang, Daming Zhu

¹Shangdong University, Ji'nan, P.R. China.

IEEE/ACM Transactions on Computational Biology and Bioinformatics

|February 5, 2008

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

Investigations on Multiple Protein Scaffold Filling.

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

Same author

Electrolyte-Regulated Epitaxial-Like Gradient Interface for Stable 4.8 V LiCoO<sub>2</sub>.

Journal of the American Chemical Society·2026

Same author

<i>Mycobacterium abscessus</i> bacteremia complicated by sepsis and septic shock in a patient with multiple comorbidities: a case report.

Frontiers in immunology·2026

Same author

Genomic epidemiology and antimicrobial resistance prevalence of <i>Staphylococcus aureus</i> isolated from bloodstream infections in a tertiary hospital in central China: a 5-year retrospective study.

Frontiers in public health·2026

Same author

Synergistic Interfacial and Solvation Regulation by Nicotinamide for Dendrite-Free, Deep-Cycling Zinc Metal Anodes.

Small (Weinheim an der Bergstrasse, Germany)·2026

Same author

Rapid separation of <sup>99</sup>Mo from proton irradiated thorium target for medical application.

Talanta·2026

Same journal

circ2DGNN: circRNA-Disease Association Prediction via Transformer-Based Graph Neural Network.

IEEE/ACM transactions on computational biology and bioinformatics·2024

Same journal

Hierarchical Hypergraph Learning in Association- Weighted Heterogeneous Network for miRNA- Disease Association Identification.

IEEE/ACM transactions on computational biology and bioinformatics·2024

Same journal

Discriminative Domain Adaption Network for Simultaneously Removing Batch Effects and Annotating Cell Types in Single-Cell RNA-Seq.

IEEE/ACM transactions on computational biology and bioinformatics·2024

Same journal

MLW-BFECF: A Multi-Weighted Dynamic Cascade Forest Based on Bilinear Feature Extraction for Predicting the Stage of Kidney Renal Clear Cell Carcinoma on Multi-Modal Gene Data.

IEEE/ACM transactions on computational biology and bioinformatics·2024

Same journal

An End-to-End Knowledge Graph Fused Graph Neural Network for Accurate Protein-Protein Interactions Prediction.

IEEE/ACM transactions on computational biology and bioinformatics·2024

Same journal

Generative Biomedical Event Extraction With Constrained Decoding Strategy.

IEEE/ACM transactions on computational biology and bioinformatics·2024

See all related articles

This study introduces a new approximation algorithm for genome rearrangement, specifically for unsigned translocation distance. The new method achieves a better approximation ratio than previously known algorithms.

Area of Science:

Computational Biology
Bioinformatics
Genomics

Background:

Genome rearrangement is a key area in computational biology.
Translocation is a common operation studied in genome rearrangement.
Calculating the exact unsigned translocation distance is computationally difficult (NP-hard).

Purpose of the Study:

To develop a more efficient algorithm for computing unsigned translocation distance.
To improve the approximation ratio for this NP-hard problem.

Main Methods:

The study presents a novel approximation algorithm.
The algorithm's performance is analyzed in terms of its approximation ratio and running time.

Main Results:

Related Experiment Videos

The proposed algorithm achieves a (1.5 + epsilon)-approximation ratio.

This ratio is an improvement over the previously best known 1.75-ratio.

The algorithm's running time is O(n^2 + (4/epsilon)^1.5 * log(4/epsilon)^2 * (4/epsilon)).

Conclusions:

The new algorithm offers a better approximation for unsigned translocation distance.
This advancement is significant for computational biology and bioinformatics research.
The algorithm provides a more efficient computational solution for genome rearrangement problems.