Transforming cabbage into turnip

DOI10.1145/300515.300516zbMath1064.92510OpenAlexW1989978323MaRDI QIDQ3158530

Pavel A. Pevzner, Sridhar Hannenhalli

Publication date: 25 January 2005

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/300515.300516

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Permutations, words, matrices (05A05) Biochemistry, molecular biology (92C40)

Related Items (only showing first 100 items - show all)

Low-dimensional topology. Abstracts from the workshop held January 15--21, 2023 ⋮ Rearrangement events on circular genomes ⋮ On the class of double distance problems ⋮ An algebraic model for inversion and deletion in bacterial genome rearrangement ⋮ Invertibility of Digraphs and Tournaments ⋮ Unnamed Item ⋮ On the complexity of unsigned translocation distance ⋮ Efficient algorithms for multichromosomal genome rearrangements. ⋮ A topological framework for signed permutations ⋮ The complexity of genome rearrangement combinatorics under the infinite sites model ⋮ Heuristics for Reversal Distance Between Genomes with Duplicated Genes ⋮ AVERAGE-CASE ANALYSIS OF PERFECT SORTING BY REVERSALS ⋮ Computing the Rearrangement Distance of Natural Genomes ⋮ Estimating the expected reversal distance after a fixed number of reversals ⋮ Approximation algorithms for sorting permutations by length-weighted short rearrangements ⋮ (Prefix) reversal distance for (signed) strings with few blocks or small alphabets ⋮ 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 ⋮ Entropic fluctuations in DNA sequences ⋮ Prefix and suffix reversals on strings ⋮ The evolution of the random reversal graph ⋮ Sorting by \(k\)-cuts on signed permutations ⋮ A new approach for the reversal distance with indels and moves in intergenic regions ⋮ Approximating reversal distance for strings with bounded number of duplicates ⋮ Aligning and Labeling Genomes under the Duplication-Loss Model ⋮ Advances on sorting by reversals ⋮ Structural properties and tractability results for linear synteny ⋮ A lower bound for the breakpoint phylogeny problem ⋮ Improved upper bound for sorting permutations by prefix transpositions ⋮ Permutation patterns in genome rearrangement problems: the reversal model ⋮ Sorting genomes by generalized translocations ⋮ Sorting by reversals and the theory of 4-regular graphs ⋮ Prefix and Suffix Reversals on Strings ⋮ A 1.375-approximation algorithm for unsigned translocation sorting ⋮ Sorting by prefix block-interchanges ⋮ On the approximability of the exemplar adjacency number problem for genomes with gene repetitions ⋮ Lengths of cycles in generalized pancake graphs ⋮ An Algorithm to Enumerate Grid Signed Permutation Classes ⋮ Random induced subgraphs of Cayley graphs induced by transpositions ⋮ Sorting permutations: Games, genomes, and cycles ⋮ A new approximation algorithm for sorting of signed permutations ⋮ Successor rules for flipping pancakes and burnt pancakes ⋮ An efficient algorithm for one-sided block ordering problem under block-interchange distance ⋮ Successful pressing sequences for a bicolored graph and binary matrices ⋮ Polynomial-time sortable stacks of burnt pancakes ⋮ On the flip graphs on perfect matchings of complete graphs and signed reversal graphs ⋮ On the inapproximability of the exemplar conserved interval distance problem of genomes ⋮ Adjacent Swaps on Strings ⋮ Alignments of mitochondrial genome arrangements: applications to metazoan phylogeny ⋮ A representation-theoretic approach to the calculation of evolutionary distance in bacteria ⋮ Girth of pancake graphs ⋮ Effect of scale on long-range random graphs and chromosomal inversions ⋮ Breakpoint distance and PQ-trees ⋮ The distribution of cycles in breakpoint graphs of signed permutations ⋮ Sequential vs. Parallel complexity in simple gene assembly ⋮ A linear time algorithm for the inversion median problem in circular bacterial genomes ⋮ An \(O(n^{3/2}\sqrt {\log (n)})\) algorithm for sorting by reciprocal translocations ⋮ An algebraic view of bacterial genome evolution ⋮ Improved bounds on sorting by length-weighted reversals ⋮ Approximating Shortest Connected Graph Transformation for Trees ⋮ The fibers and range of reduction graphs in ciliates ⋮ Maximum likelihood estimates of rearrangement distance: implementing a representation-theoretic approach ⋮ Pancake flipping is hard ⋮ Approximation algorithms for sorting by length-weighted prefix and suffix operations ⋮ Comparing bacterial genomes from linear orders of patterns ⋮ Expected number of breakpoints after \(t\) random reversals in genomes with duplicate genes ⋮ Quick Greedy Computation for Minimum Common String Partitions ⋮ An Evolutionary Distance Based on Maximal Unique Matches ⋮ Word length perturbations in certain symmetric presentations of dihedral groups ⋮ Some problems on Cayley graphs ⋮ Sorting permutations and binary strings by length-weighted rearrangements ⋮ Uniquely pressable graphs: characterization, enumeration, and recognition ⋮ An algorithm with linear expected running time for string editing with substitutions and substring reversals ⋮ The `Butterfly effect' in Cayley graphs with applications to genomics. ⋮ A 14/11-approximation algorithm for sorting by short block-moves ⋮ A very elementary presentation of the Hannenhalli-Pevzner theory ⋮ Cycles in the burnt pancake graph ⋮ On maximal instances for the original syntenic distance ⋮ A simpler and faster 1.5-approximation algorithm for sorting by transpositions ⋮ Signed genome rearrangement by reversals and transpositions: Models and approximations ⋮ Quick greedy computation for minimum common string partition ⋮ Some relations on prefix reversal generators of the symmetric and hyperoctahedral group ⋮ Sorting signed permutations by reversals, revisited ⋮ Statistical and Combinatorial Aspects of Comparative Genomics* ⋮ Pivots, determinants, and perfect matchings of graphs ⋮ Genome rearrangements with partially ordered chromosomes ⋮ A sparse dynamic programming algorithm for alignment with non-overlapping inversions ⋮ Length-weighted \(\lambda\)-rearrangement distance ⋮ An improved algorithm for sorting by block-interchanges based on permutation groups ⋮ Moduli spaces and macromolecules ⋮ Sorting a permutation by best short swaps ⋮ New Genome Similarity Measures Based on Conserved Gene Adjacencies ⋮ Plane Permutations and Applications to a Result of Zagier--Stanley and Distances of Permutations ⋮ Average-Case Analysis of Perfect Sorting by Reversals ⋮ Reversal and transposition medians ⋮ Reversal distance on genomes with different gene content and intergenic regions information ⋮ Reversals distance considering flexible intergenic regions sizes ⋮ Unnamed Item ⋮ A new linear time algorithm to compute the genomic distance via the double cut and join distance ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics

This page was built for publication: Transforming cabbage into turnip