scientific article

zbMath1170.92022MaRDI QIDQ3393448

Eric Tannier, Stéphane Vialette, Anthony Labarre, Irena Rusu, Guillaume Fertin

Publication date: 26 August 2009

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Problems related to evolution (92D15) Combinatorial optimization (90C27) Biochemistry, molecular biology (92C40) Research exposition (monographs, survey articles) pertaining to biology (92-02)

Related Items (79)

The complexity of genome rearrangement combinatorics under the infinite sites model ⋮ Models and Algorithms for Genome Rearrangement with Positional Constraints ⋮ Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution ⋮ Heuristics for Reversal Distance Between Genomes with Duplicated Genes ⋮ Sorting by multi-cut rearrangements ⋮ Greedy flipping of pancakes and burnt pancakes ⋮ (Prefix) reversal distance for (signed) strings with few blocks or small alphabets ⋮ Median approximations for genomes modeled as matrices ⋮ Sorting on graphs by adjacent swaps using permutation groups ⋮ A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation ⋮ Metric intersection problems in Cayley graphs and the Stirling recursion ⋮ La distance de réarrangement, duale de la fonctionnelle de Bowen ⋮ Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps ⋮ Prefix and suffix reversals on strings ⋮ Comparative Genomics on Artificial Life ⋮ The evolution of the random reversal graph ⋮ Sorting by \(k\)-cuts on signed permutations ⋮ Maximum likelihood estimates of pairwise rearrangement distances ⋮ Aligning and Labeling Genomes under the Duplication-Loss Model ⋮ The parameterized complexity of local search for TSP, more refined ⋮ Asymptotic medians of random permutations sampled from reversal random walks ⋮ Computing similarity distances between rankings ⋮ Sorting by Cuts, Joins and Whole Chromosome Duplications ⋮ Sorting with forbidden intermediates ⋮ Complete edge-colored permutation graphs ⋮ Longest increasing subsequences and log concavity ⋮ Sorting by reversals and the theory of 4-regular graphs ⋮ Prefix and Suffix Reversals on Strings ⋮ Sorting by prefix block-interchanges ⋮ On the role of metaheuristic optimization in bioinformatics ⋮ Rearrangement events on circular genomes ⋮ The floor is lava -- halving genomes with viaducts, piers and pontoons ⋮ Sorting permutations: Games, genomes, and cycles ⋮ Sorting genomes by prefix double-cut-and-joins ⋮ An algebraic model for inversion and deletion in bacterial genome rearrangement ⋮ Successor rules for flipping pancakes and burnt pancakes ⋮ An efficient algorithm for one-sided block ordering problem under block-interchange distance ⋮ New applications of interval generators to genome comparison ⋮ Invertibility of Digraphs and Tournaments ⋮ Polynomial-time sortable stacks of burnt pancakes ⋮ Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality ⋮ Flipping edge-labelled triangulations ⋮ Sorting signed permutations by reversals using link-cut trees ⋮ Approximating the number of double cut-and-join scenarios ⋮ Girth of pancake graphs ⋮ Revisiting the parameterized complexity of maximum-duo preservation string mapping ⋮ Unnamed Item ⋮ The distribution of cycles in breakpoint graphs of signed permutations ⋮ An algebraic view of bacterial genome evolution ⋮ Sorting by prefix reversals and prefix transpositions ⋮ Sorting permutations with transpositions in \(O(n^3)\) amortized time ⋮ Crossings and nestings for arc-coloured permutations and automation ⋮ Maximum likelihood estimates of rearrangement distance: implementing a representation-theoretic approach ⋮ Tighter upper bound for sorting permutations with prefix transpositions ⋮ Approximation algorithms for sorting by length-weighted prefix and suffix operations ⋮ Sorting by Transpositions Is Difficult ⋮ Sorting permutations and binary strings by length-weighted rearrangements ⋮ Length two path centered surface areas of the \((n, k)\)-star graph ⋮ Uniquely pressable graphs: characterization, enumeration, and recognition ⋮ The `Butterfly effect' in Cayley graphs with applications to genomics. ⋮ Maximum cycle packing in Eulerian graphs using local traces ⋮ Packing Euler graphs with traces ⋮ Some relations on prefix reversal generators of the symmetric and hyperoctahedral group ⋮ On the hardness of maximum rank aggregation problems ⋮ Extremal permutations in routing cycles ⋮ Group-theoretic models of the inversion process in bacterial genomes ⋮ \(\log\)-lists and their applications to sorting by transpositions, reversals and block-interchanges ⋮ On the effective and automatic enumeration of polynomial permutation classes ⋮ Fixed-parameter algorithms for scaffold filling ⋮ Counting and sampling SCJ small parsimony solutions ⋮ On the computational complexity of closest genome problems ⋮ Reversal distance on genomes with different gene content and intergenic regions information ⋮ An Audit Tool for Genome Rearrangement Algorithms ⋮ Bounding prefix transposition distance for strings and permutations ⋮ Rearrangements in Phylogenetic Inference: Compare, Model, or Encode? ⋮ The Potential of Family-Free Genome Comparison ⋮ Bacterial phylogeny in the Cayley graph ⋮ Approximation algorithms for sorting by \(k\)-cuts on signed permutations ⋮ A Hamilton cycle in the \(k\)-sided pancake network

This page was built for publication: