Reversals and Transpositions Over Finite Alphabets

DOI10.1137/S0895480103433550zbMath1086.68094MaRDI QIDQ5317611

Elizabeth L. Wilmer, Alexander D. Scott, Andrew John Radcliffe

Publication date: 16 September 2005

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

sortingNP-complete problemsstringsapproximation algorithmstranspositionsreversalsgenome comparisonMAX-SNP hardness

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Combinatorics on words (68R15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (14)

Heuristics for Reversal Distance Between Genomes with Duplicated Genes ⋮ A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ (Prefix) reversal distance for (signed) strings with few blocks or small alphabets ⋮ Prefix and suffix reversals on strings ⋮ A new approach for the reversal distance with indels and moves in intergenic regions ⋮ Prefix and Suffix Reversals on Strings ⋮ Signed rearrangement distances considering repeated genes, intergenic regions, and indels ⋮ Multi-break rearrangements and chromosomal evolution ⋮ Multiple genome rearrangement by swaps and by element duplications ⋮ Prefix and suffix transreversals on binary and ternary strings ⋮ Sorting by Transpositions Is Difficult ⋮ Transposition Rearrangement: Linear Algorithm for Length-Cost Model ⋮ UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE ⋮ Bounding prefix transposition distance for strings and permutations

This page was built for publication: Reversals and Transpositions Over Finite Alphabets