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 1.375-approximation algorithm for sorting by transpositions.

Isaac Elias1, Tzvika Hartman

  • 1Department of Numerical Analysis and Computer Science, Royal Institute of Technology, Stockholm, Sweden. isaac@nada.kth.se

IEEE/ACM Transactions on Computational Biology and Bioinformatics
|November 7, 2006
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

Improved electronic uniformity and nanoscale homogeneity in template-grown CsPbBr<sub>3</sub> nanorods.

Nanoscale·2024
Same author

Yield of diagnostic testing in evaluating etiology and end organ effects of pediatric hypertension.

Pediatric nephrology (Berlin, Germany)·2023
Same author

Active deep learning to detect demographic traits in free-form clinical notes.

Journal of biomedical informatics·2020
Same author

Customization scenarios for de-identification of clinical notes.

BMC medical informatics and decision making·2020
Same author

Multiple sclerosis risk perception and acceptance for Brazilian patients.

Arquivos de neuro-psiquiatria·2018
Same author

Fastphylo: fast tools for phylogenetics.

BMC bioinformatics·2013
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

Researchers developed a new 1.375-approximation algorithm for sorting permutations using transpositions, improving upon the previous 1.5-approximation. This advancement in computational biology addresses a decade-old challenge in genome rearrangements.

Area of Science:

  • Computational Biology
  • Genomics
  • Algorithm Analysis

Background:

  • Sorting permutations by transpositions is a key problem in genome rearrangements.
  • The computational complexity remains an open question.
  • The best-known algorithm offers a 1.5-approximation.

Purpose of the Study:

  • To develop an improved approximation algorithm for sorting by transpositions.
  • To establish a new upper bound for the diameter of 3-permutations.
  • To advance understanding of transposition diameter in permutation groups.

Main Methods:

  • Developed a novel algorithm achieving a 1.375-approximation ratio.
  • Established a new upper bound for the diameter of 3-permutations.
  • Investigated transposition diameters within the symmetric group and for simple permutations.

Related Experiment Videos

Main Results:

  • Introduced a 1.375-approximation algorithm for sorting by transpositions.
  • Derived a new upper bound on the diameter of 3-permutations.
  • Improved the lower bound for the transposition diameter of the symmetric group.
  • Determined the exact transposition diameter for simple permutations.

Conclusions:

  • The new algorithm offers a significant improvement in approximating sorting by transpositions.
  • The findings contribute to solving a long-standing open problem in genome rearrangements.
  • Further research into permutation diameters can yield advancements in computational biology.