A new linear time algorithm to compute the genomic distance via the double cut and join distance

DOI10.1016/j.tcs.2009.09.008zbMath1186.68144OpenAlexW2152404552MaRDI QIDQ1038470

Anne Bergeron, Julia Mixtacki, Jens Stoye

Publication date: 18 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2010/2689/

zbMATH Keywords

comparative genomicsgenome rearrangementsfusionsgenomic distance computationsorting by translocations

Mathematics Subject Classification ID

Searching and sorting (68P10) Computing methodologies and applications (68U99)

Related Items (6)

Can a breakpoint graph be decomposed into none other than 2-cycles? ⋮ Balanced vertices in trees and a simpler algorithm to compute the genomic distance ⋮ Linear algorithm for a cyclic graph transformation ⋮ The `Butterfly effect' in Cayley graphs with applications to genomics. ⋮ New Genome Similarity Measures Based on Conserved Gene Adjacencies ⋮ Rearrangements in Phylogenetic Inference: Compare, Model, or Encode?

Uses Software

• GRIMM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for multichromosomal genome rearrangements.
• Genome rearrangements: a correct algorithm for optimal capping
• On the Similarity of Sets of Permutations and Its Applications to Genome Comparison
• Transforming cabbage into turnip
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• Combinatorial Pattern Matching

This page was built for publication: A new linear time algorithm to compute the genomic distance via the double cut and join distance