Combinatorics of genome rearrangements.

zbMATH Open1170.92022MaRDI QIDQ3393448FDOQ3393448

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

Publication date: 26 August 2009

Recommendations

• scientific article; zbMATH DE number 1728477
• scientific article; zbMATH DE number 776086
• Statistical and Combinatorial Aspects of Comparative Genomics*
• Selected combinatorial problems of computational biology
• The complexity of genome rearrangement combinatorics under the infinite sites model

Mathematics Subject Classification ID

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

Cited In (98)

• On the effective and automatic enumeration of polynomial permutation classes
• The complexity of genome rearrangement combinatorics under the infinite sites model
• Sorting by multi-cut rearrangements
• Group-theoretic models of the inversion process in bacterial genomes
• Maximum likelihood estimates of rearrangement distance: implementing a representation-theoretic approach
• Sorting permutations with transpositions in \(O(n^3)\) amortized time
• A Hamilton cycle in the \(k\)-sided pancake network
• New applications of interval generators to genome comparison
• Sorting permutations and binary strings by length-weighted rearrangements
• Flipping edge-labelled triangulations
• Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution
• Title not available (Why is that?)
• Aligning and Labeling Genomes under the Duplication-Loss Model
• Maximum likelihood estimates of pairwise rearrangement distances
• Models and algorithms for genome rearrangement with positional constraints
• Greedy flipping of pancakes and burnt pancakes
• An audit tool for genome rearrangement algorithms
• Approximating the number of double cut-and-join scenarios
• Median approximations for genomes modeled as matrices
• Extremal permutations in routing cycles
• \(\log\)-lists and their applications to sorting by transpositions, reversals and block-interchanges
• Counting and sampling SCJ small parsimony solutions
• Prefix and suffix reversals on strings
• Successor rules for flipping pancakes and burnt pancakes
• Heuristics for reversal distance between genomes with duplicated genes
• Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps
• Prefix and Suffix Reversals on Strings
• An efficient algorithm for one-sided block ordering problem under block-interchange distance
• Length two path centered surface areas of the \((n, k)\)-star graph
• The `Butterfly effect' in Cayley graphs with applications to genomics.
• An algebraic view of bacterial genome evolution
• Sorting by prefix reversals and prefix transpositions
• Comparative genomics on artificial life
• Asymptotic medians of random permutations sampled from reversal random walks
• A small trip in the untranquil world of genomes: a survey on the detection and analysis of genome rearrangement breakpoints
• On the hardness of maximum rank aggregation problems
• Bounding prefix transposition distance for strings and permutations
• Reversal distance on genomes with different gene content and intergenic regions information
• (Prefix) reversal distance for (signed) strings with few blocks or small alphabets
• Title not available (Why is that?)
• Longest increasing subsequences and log concavity
• Sorting by reversals and the theory of 4-regular graphs
• Approximation algorithms for sorting by \(k\)-cuts on signed permutations
• Crossings and nestings for arc-coloured permutations and automation
• Sorting by \(k\)-cuts on signed permutations
• Girth of pancake graphs
• The combinatorics of tandem duplication
• Polynomial-time sortable stacks of burnt pancakes
• Tighter upper bound for sorting permutations with prefix transpositions
• Approximation algorithms for sorting by length-weighted prefix and suffix operations
• The distribution of cycles in breakpoint graphs of signed permutations
• Sorting signed permutations by reversals using link-cut trees
• Fixed-parameter algorithms for scaffold filling
• The parameterized complexity of local search for TSP, more refined
• Comparative Genomics
• Uniquely pressable graphs: characterization, enumeration, and recognition
• Bacterial phylogeny in the Cayley graph
• The potential of family-free genome comparison
• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• Metric intersection problems in Cayley graphs and the Stirling recursion
• Title not available (Why is that?)
• Invertibility of Digraphs and Tournaments
• Rearrangements in phylogenetic inference: compare, model, or encode?
• An algebraic model for inversion and deletion in bacterial genome rearrangement
• Statistical and Combinatorial Aspects of Comparative Genomics*
• Some relations on prefix reversal generators of the symmetric and hyperoctahedral group
• The distance of rearrangement, the dual functional of Bowen
• Sorting by prefix block-interchanges
• Cabbage can't always be transformed into turnip: decision algorithms for sorting by symmetric reversals
• Title not available (Why is that?)
• Sorting by Cuts, Joins and Whole Chromosome Duplications
• On the role of metaheuristic optimization in bioinformatics
• Sorting permutations: games, genomes, and cycles
• Maximum cycle packing in Eulerian graphs using local traces
• Sorting signed permutations by tandem duplication random loss and inverse tandem duplication random loss
• A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation
• Rearrangement events on circular genomes
• The \textsc{maximum zero-sum partition} problem
• Some integer values in the spectra of burnt pancake graphs
• The floor is lava -- halving genomes with viaducts, piers and pontoons
• The evolution of the random reversal graph
• Sorting genomes by prefix double-cut-and-joins
• Complete edge-colored permutation graphs
• Complexity and enumeration in models of genome rearrangement
• Combinatorics of chromosomal rearrangements based on synteny blocks and synteny packs
• Exact and approximation algorithms for the contiguous translocation distance problem
• Distances in graphs of permutations
• Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality
• On the computational complexity of closest genome problems
• Computing similarity distances between rankings
• Permutation-constrained common string partitions with applications
• The Combinatorics of Sequencing the Corn Genome
• Sorting on graphs by adjacent swaps using permutation groups
• Constant time and space updates for the sigma-tau problem
• Generating signed permutations by twisting two-sided ribbons
• Sorting genomes by prefix double-cut-and-joins
• Title not available (Why is that?)
• Packing Euler graphs with traces

This page was built for publication: Combinatorics of genome rearrangements.

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