A NOTE ON COMPLEXITY OF GENETIC MUTATIONS
From MaRDI portal
Publication:2890984
DOI10.1142/S1793830911001206zbMath1252.68136OpenAlexW1979149097WikidataQ56287380 ScholiaQ56287380MaRDI QIDQ2890984
Publication date: 12 June 2012
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s1793830911001206
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)
Related Items (6)
(Prefix) reversal distance for (signed) strings with few blocks or small alphabets ⋮ Approximation algorithms for sorting permutations by extreme block-interchanges ⋮ UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE ⋮ Layered graphs: applications and algorithms ⋮ Exact upper bound for sorting Rn with LE ⋮ Bounding prefix transposition distance for strings and permutations
Cites Work
- On the complexity of unsigned translocation distance
- An \((18/11)n\) upper bound for sorting by prefix reversals
- Approximating reversal distance for strings with bounded number of duplicates
- Bounds for sorting by prefix reversal
- A 2-approximation algorithm for genome rearrangements by reversals and transpositions
- On the inapproximability of the exemplar conserved interval distance problem of genomes
- Edit distance with move operations
- Short proofs for cut-and-paste sorting of permutations
- Sorting Strings by Reversals and by Transpositions
- The greedy algorithm for the minimum common string partition problem
- Adjacent Swaps on Strings
- Prefix Reversals on Binary and Ternary Strings
- Minimum Common String Partition Revisited
- On the Approximability of Comparing Genomes with Duplicates
- Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems
- `` Strong NP-Completeness Results
- On the Diameter of the Pancake Network
- Reversals and Transpositions Over Finite Alphabets
- Polynomial-time algorithm for computing translocation distance between genomes
This page was built for publication: A NOTE ON COMPLEXITY OF GENETIC MUTATIONS
