A note on complexity of genetic mutations

DOI10.1142/S1793830911001206zbMATH Open1252.68136DBLPjournals/dmaa/Chitturi11OpenAlexW1979149097WikidataQ56287380 ScholiaQ56287380MaRDI QIDQ2890984FDOQ2890984

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

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

zbMATH Keywords

complexitymutationreductiongenetic distancestring transformation

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

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

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)