Reversals and Transpositions Over Finite Alphabets
From MaRDI portal
Publication:5317611
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)
sortingNP-complete problemsstringsapproximation algorithmstranspositionsreversalsgenome comparisonMAX-SNP hardness
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
