Genome Rearrangements and Sorting by Reversals
From MaRDI portal
Publication:4877518
DOI10.1137/S0097539793250627zbMath0844.68123MaRDI QIDQ4877518
Vineet Bafna, Pavel A. Pevzner
Publication date: 5 September 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Related Items
On the complexity of unsigned translocation distance ⋮ A topological framework for signed permutations ⋮ The spectral gap of graphs arising from substring reversals ⋮ The complexity of genome rearrangement combinatorics under the infinite sites model ⋮ Sorting by multi-cut rearrangements ⋮ Estimating the expected reversal distance after a fixed number of reversals ⋮ APPROXIMATE BLOCK SORTING ⋮ Hardness and approximation of traffic grooming ⋮ (Prefix) reversal distance for (signed) strings with few blocks or small alphabets ⋮ A bound for the reversal distance of genome rearrangements ⋮ Position and content paradigms in genome rearrangements: the wild and crazy world of permutations in genomics ⋮ Sorting on graphs by adjacent swaps using permutation groups ⋮ Signed Hultman numbers and signed generalized commuting probability in finite groups ⋮ On sorting unsigned permutations by double-cut-and-joins ⋮ Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles) ⋮ Can a breakpoint graph be decomposed into none other than 2-cycles? ⋮ Estimate the distance of genome rearrangements by reversals ⋮ Optimal algorithms for uncovering synteny problem ⋮ The structure of Cayley graphs of dihedral groups of Valencies 1, 2 and 3 ⋮ Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement ⋮ Two-sided Group Digraphs and Graphs ⋮ A 1.75-approximation algorithm for unsigned translocation distance ⋮ Edge-Disjoint Packing of Stars and Cycles ⋮ Structural properties and tractability results for linear synteny ⋮ A mean first passage time genome rearrangement distance ⋮ Algebraic double cut and join: A group-theoretic approach to the operator on multichromosomal genomes ⋮ Sorting by reversals and the theory of 4-regular graphs ⋮ On the average number of reversals needed to sort signed permutations ⋮ Rearrangement events on circular genomes ⋮ On the class of double distance problems ⋮ Sorting genomes by prefix double-cut-and-joins ⋮ A new approximation algorithm for sorting of signed permutations ⋮ An approximation algorithm for genome sorting by reversals to recover all adjacencies ⋮ Invertibility of Digraphs and Tournaments ⋮ Polynomial-time sortable stacks of burnt pancakes ⋮ The transposition median problem is NP-complete ⋮ The distribution of cycles in breakpoint graphs of signed permutations ⋮ An algebraic view of bacterial genome evolution ⋮ Improved bounds on sorting by length-weighted reversals ⋮ Block Sorting is Hard ⋮ Multi-break rearrangements and chromosomal evolution ⋮ Sorting by prefix reversals and prefix transpositions ⋮ Edit distance with move operations ⋮ On minimal generating sets for symmetric and alternating groups ⋮ Pancake flipping and sorting permutations ⋮ Pancake flipping is hard ⋮ Reconstruction of permutations distorted by reversal errors ⋮ CIRCULAR INVERSIONS OF PERMUTATIONS AND THEIR USE IN SORTING PROBLEMS ⋮ Sorting permutations by block-interchanges ⋮ Two examples of Wilf-collapse ⋮ Word length perturbations in certain symmetric presentations of dihedral groups ⋮ Some problems on Cayley graphs ⋮ Sorting permutations and binary strings by length-weighted rearrangements ⋮ The `Butterfly effect' in Cayley graphs with applications to genomics. ⋮ String factorisations with maximum or minimum dimension ⋮ Maximum cycle packing in Eulerian graphs using local traces ⋮ A 14/11-approximation algorithm for sorting by short block-moves ⋮ Packing Euler graphs with traces ⋮ On maximal instances for the original syntenic distance ⋮ A simpler and faster 1.5-approximation algorithm for sorting by transpositions ⋮ An algorithm for reversal median problem ⋮ Signed genome rearrangement by reversals and transpositions: Models and approximations ⋮ Sorting signed permutations by reversals, revisited ⋮ On sorting by 3-bounded transpositions ⋮ Group-theoretic models of the inversion process in bacterial genomes ⋮ Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles) ⋮ Polynomial-time algorithm for computing translocation distance between genomes ⋮ Sorting with fixed-length reversals ⋮ Sorting a permutation by best short swaps ⋮ A quadratic time 2-approximation algorithm for block sorting ⋮ Vertex reconstruction in Cayley graphs ⋮ Compatible cycles and CHY integrals ⋮ Plane Permutations and Applications to a Result of Zagier--Stanley and Distances of Permutations ⋮ An approximation algorithm for sorting by reversals and transpositions ⋮ On approximating four covering and packing problems ⋮ Reversal and transposition medians ⋮ Reversal distance on genomes with different gene content and intergenic regions information ⋮ Reversals distance considering flexible intergenic regions sizes ⋮ A 2-approximation algorithm for genome rearrangements by reversals and transpositions ⋮ Weighted Minimum-Length Rearrangement Scenarios. ⋮ An Audit Tool for Genome Rearrangement Algorithms ⋮ Bounding prefix transposition distance for strings and permutations ⋮ On the complexity and approximation of syntenic distance ⋮ Sorting by bounded block-moves ⋮ Reconstructing a history of recombinations from a set of sequences ⋮ Intersection graphs of general linear groups ⋮ An improved genetic algorithm for problem of genome rearrangement ⋮ Unnamed Item ⋮ The Emperor Has No Caps! A Comparison of DCJ and Algebraic Distances ⋮ Generating a random signed permutation with random reversals ⋮ Packing triangles in bounded degree graphs. ⋮ \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.
