scientific article; zbMATH DE number 910920

MaRDI QIDQ4886097zbMATH OpenFDO

Authors Vineet Bafna, Pavel Pevzner

Publication date 30 September 1996

zbMATH Keywords

permutationsapproximation algorithmssymmetric groupsequence alignmentgenome comparisongenome rearrangementssorting by transpositionsalignment algorithmsgene comparisonlower bounds on transposition distance

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Combinatorics in computer science (68R05) Searching and sorting (68P10)

Recommendations

• Sorting by Transpositions
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• scientific article; zbMATH DE number 1342319
• Genome Rearrangements and Sorting by Reversals

Cited in

(31)

• Sorting permutations by block-interchanges
• Reversal distance on genomes with different gene content and intergenic regions information
• Sorting permutations with transpositions in \(O(n^3)\) amortized time
• STEINER POINTS IN THE SPACE OF GENOME REARRANGEMENTS
• On sorting by 3-bounded transpositions
• Counting sorting scenarios and intermediate genomes for the rank distance
• Finding all sorting tandem duplication random loss operations
• The complexity of genome rearrangement combinatorics under the infinite sites model
• An algorithm for reversal median problem
• Sorting with fixed-length reversals
• Sorting strings by reversals and by transpositions
• Distances in graphs of permutations
• Transposition rearrangement: linear algorithm for length-cost model
• Estimate the distance of genome rearrangements by reversals
• Bacterial phylogeny in the Cayley graph
• Sorting signed permutations by tandem duplication random loss and inverse tandem duplication random loss
• Steps toward accurate reconstructions of phylogenies from gene-order data.
• Interchanging graphs associated with sorting by transpositions
• Polynomial-time algorithm for computing translocation distance between genomes
• Plane permutations and applications to a result of Zagier-Stanley and distances of permutations
• Sorting permutations by limited-size operations
• scientific article; zbMATH DE number 7286740 (Why is no real title available?)
• On the complexity and approximation of syntenic distance
• Sorting of Permutations by Cost-Constrained Transpositions
• A simpler 1.5-approximation algorithm for sorting by transpositions
• Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles)
• Reconstructing a history of recombinations from a set of sequences
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• Two permutation classes related to the bubble sort operator
• Sorting by prefix reversals and prefix transpositions

This page was built for publication:

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