Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
type: Item
instance of: scholarly article
title: Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
zbMATH Open document ID: 0831.92014
DOI: 10.1007/BF01188586
author: David Sankoff
author: John D. Kececioglu
published in: Algorithmica
publication date: 1996-01-11T00:00:00Z
Mathematics Subject Classification ID: 92C40
Mathematics Subject Classification ID: 92-08
Mathematics Subject Classification ID: 92D20
Mathematics Subject Classification ID: 90C90
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68R05
zbMATH DE Number: 819150
zbMATH Keywords: experimental analysis of algorithms
zbMATH Keywords: edit distance
zbMATH Keywords: sorting by reversals
zbMATH Keywords: genome rearrangements
zbMATH Keywords: chromosome inversions
zbMATH Keywords: shortest series of reversals
zbMATH Keywords: greedy approximation algorithm
zbMATH Keywords: branch-and-bound exact algorithm
zbMATH Keywords: maximum-weight matchings
zbMATH Keywords: shortest paths
zbMATH Keywords: linear programming
zbMATH Keywords: random permutations
zbMATH Keywords: random reversals
zbMATH Keywords: mitochondrial genomes
MaRDI profile type: Publication
cites work: Sorting by insertion of leading elements
cites work: Reversing trains: A turn of the century sorting problem
cites work: Genome Rearrangements and Sorting by Reversals
cites work: Computing short generator sequences
cites work: The minimum-length generator sequence problem is NP-hard
cites work: Q3912839
cites work: Q4198056
cites work: Bounds for sorting by prefix reversal
cites work: The complexity of finding minimum-length generator sequences
cites work: Q5585020
cites work: Measures of Presortedness and Optimal Sorting Algorithms
cites work: A local algorithm for DNA sequence alignment with inversions
full work available at URL: https://doi.org/10.1007/bf01188586
OpenAlex ID: W2054600183
Recommended article: An approximation algorithm for genome sorting by reversals to recover all adjacencies
Recommended article: A 2-approximation algorithm for genome rearrangements by reversals and transpositions
Recommended article: Q4468952
Recommended article: An approximation algorithm for sorting by reversals and transpositions
Recommended article: A (1.408+ε)-Approximation Algorithm for Sorting Unsigned Genomes by Reciprocal Translocations
Recommended article: Q5456783
Recommended article: A 3.5-Approximation Algorithm for Sorting by Intergenic Transpositions
Recommended article: Genome Rearrangement Algorithms for Unsigned Permutations with O(logn) Singletons
description: scientific article; zbMATH DE number 819150