scientific article; zbMATH DE number 1263193

zbMath0978.68530MaRDI QIDQ4234063

Pavel A. Pevzner, Sridhar Hannenhalli

Publication date: 3 February 2002

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Protein sequences, DNA sequences (92D20)

Related Items

Reconstructing an ancestral genome using minimum segments duplications and reversals. ⋮ Steps toward accurate reconstructions of phylogenies from gene-order data. ⋮ Comparing Integer Linear Programming to SAT-Solving for Hard Problems in Computational and Systems Biology ⋮ Genomic distances under deletions and insertions ⋮ Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles) ⋮ Genome rearrangements: a correct algorithm for optimal capping ⋮ Exploiting pseudo-locality of interchange distance ⋮ 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 ⋮ A 1.75-approximation algorithm for unsigned translocation distance ⋮ Sorting by Cuts, Joins and Whole Chromosome Duplications ⋮ On the average number of reversals needed to sort signed permutations ⋮ An approximation algorithm for genome sorting by reversals to recover all adjacencies ⋮ A 2.25-Approximation Algorithm for Cut-and-Paste Sorting of Unsigned Circular Permutations ⋮ A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations ⋮ Walking tree heuristics for comparative genomic alignments. ⋮ Can a Breakpoint Graph be Decomposed into None Other Than 2-Cycles? ⋮ Pancake flipping and sorting permutations ⋮ Short proofs for cut-and-paste sorting of permutations ⋮ Pancake flipping is hard ⋮ Patterns of simple gene assembly in ciliates ⋮ Decision problem for shuffled genes ⋮ Finding all sorting tandem duplication random loss operations ⋮ An algorithm for reversal median problem ⋮ Reducibility of gene patterns in ciliates using the breakpoint graph. ⋮ A sparse dynamic programming algorithm for alignment with non-overlapping inversions ⋮ Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles) ⋮ Polynomial-time algorithm for computing translocation distance between genomes ⋮ Simple Operations for Gene Assembly ⋮ An approximation algorithm for sorting by reversals and transpositions ⋮ Finding All Sorting Tandem Duplication Random Loss Operations ⋮ A 2-approximation algorithm for genome rearrangements by reversals and transpositions ⋮ On the complexity and approximation of syntenic distance ⋮ Reconstructing a history of recombinations from a set of sequences ⋮ Rearrangements in Phylogenetic Inference: Compare, Model, or Encode? ⋮ General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic ⋮ \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.