A note on complexity of genetic mutations

DOI10.1142/S1793830911001206MaRDI QIDQ2890984zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Bhadrachalam Chitturi

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

zbMATH Keywords

complexitygenetic distancemutationreductionstring transformation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Recommendations

• Solution to motif finding problem in membranes
• Theoretical and computational properties of transpositions
• An efficient algorithm for computing non-overlapping inversion and transposition distance
• Two-string consensus problem under non-overlapping inversion and transposition distance
• DNA Computing

Cites work

• `` Strong NP-Completeness Results
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• Adjacent Swaps on Strings
• An (18/11)n upper bound for sorting by prefix reversals
• Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems
• Approximating reversal distance for strings with bounded number of duplicates
• Bounds for sorting by prefix reversal
• Edit distance with move operations
• Minimum common string partition revisited
• On the Approximability of Comparing Genomes with Duplicates
• On the complexity of unsigned translocation distance
• On the Diameter of the Pancake Network
• On the inapproximability of the exemplar conserved interval distance problem of genomes
• Polynomial-time algorithm for computing translocation distance between genomes
• Prefix Reversals on Binary and Ternary Strings
• Reversals and Transpositions Over Finite Alphabets
• 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

Cited in

(12)

• Approximation algorithms for sorting permutations by extreme block-interchanges
• Layered graphs: applications and algorithms
• (Prefix) reversal distance for (signed) strings with few blocks or small alphabets
• On the complexity of average path length for biological networks and patterns
• Solution to motif finding problem in membranes
• Mutation Systems
• scientific article; zbMATH DE number 1305428 (Why is no real title available?)
• Upper bounds for sorting permutations with a transposition tree
• Exact upper bound for sorting \(R_n\) with LE
• A basic model of mutations
• Experimental efficiency of programmed mutagenesis
• Bounding prefix transposition distance for strings and permutations

This page was built for publication: A note on complexity of genetic mutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2890984)