Polynomial-time algorithm for computing translocation distance between genomes
From MaRDI portal
Publication:5961622
DOI10.1016/S0166-218X(96)00061-3zbMath0881.92020OpenAlexW2068426944MaRDI QIDQ5961622
Publication date: 25 February 1997
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://www.elsevier.com/locate/dam
Problems related to evolution (92D15) Applications of graph theory (05C90) Biochemistry, molecular biology (92C40) Genetics and epigenetics (92D10) Complexity and performance of numerical algorithms (65Y20)
Related Items
On the complexity of unsigned translocation distance ⋮ Reconstructing an ancestral genome using minimum segments duplications and reversals. ⋮ The spectral gap of graphs arising from substring reversals ⋮ A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ Exploiting pseudo-locality of interchange distance ⋮ Can a breakpoint graph be decomposed into none other than 2-cycles? ⋮ A 1.75-approximation algorithm for unsigned translocation distance ⋮ Sorting by Cuts, Joins and Whole Chromosome Duplications ⋮ Sorting genomes by generalized translocations ⋮ A 1.375-approximation algorithm for unsigned translocation sorting ⋮ An efficient algorithm for one-sided block ordering problem under block-interchange distance ⋮ A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations ⋮ An \(O(n^{3/2}\sqrt {\log (n)})\) algorithm for sorting by reciprocal translocations ⋮ Edit distance with move operations ⋮ Edit distance with block deletions ⋮ A 14/11-approximation algorithm for sorting by short block-moves ⋮ An improved algorithm for sorting by block-interchanges based on permutation groups ⋮ Sorting with fixed-length reversals ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics ⋮ The complexity of string partitioning
Cites Work
