scientific article; zbMATH DE number 910919

MaRDI QIDQ4886096zbMATH OpenFDO

Authors R. Ravi, John D. Kececioglu

Publication date 22 August 1996

zbMATH Keywords

2-approximation algorithmcombinatorial algorithmsgenome rearrangementsinversionoptimal algorithmrearrangement distancetranslocationtranslocation distance

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Biochemistry, molecular biology (92C40) Problems related to evolution (92D15)

Recommendations

• Polynomial-time algorithm for computing translocation distance between genomes
• Research in Computational Molecular Biology
• Structural, Syntactic, and Statistical Pattern Recognition
• Combinatorial Pattern Matching
• Sorting by Transpositions

Cited in

(29)

• Probabilistic models of genome shuffling
• On the complexity and approximation of syntenic distance
• Reconstructing a history of recombinations from a set of sequences
• Position and content paradigms in genome rearrangements: the wild and crazy world of permutations in genomics
• Reconstructing an ancestral genome using minimum segments duplications and reversals.
• Efficient algorithms for multichromosomal genome rearrangements.
• A 1.375-approximation algorithm for unsigned translocation sorting
• Genome rearrangements with partially ordered chromosomes
• Can a breakpoint graph be decomposed into none other than 2-cycles?
• A 1.75-approximation algorithm for unsigned translocation distance
• scientific article; zbMATH DE number 1728477 (Why is no real title available?)
• Sorting genomes by generalized translocations
• scientific article; zbMATH DE number 1301599 (Why is no real title available?)
• Can a breakpoint graph be decomposed into none other than 2-cycles?
• Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles)
• CIRCULAR INVERSIONS OF PERMUTATIONS AND THEIR USE IN SORTING PROBLEMS
• Combinatorial Pattern Matching
• Transposition rearrangement: linear algorithm for length-cost model
• Comparative Genomics
• Research in Computational Molecular Biology
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
• Polynomial-time algorithm for computing translocation distance between genomes
• An \(O(n^{3/2}\sqrt {\log (n)})\) algorithm for sorting by reciprocal translocations
• Exact and approximation algorithms for the contiguous translocation distance problem
• Sorting permutations by block-interchanges
• A randomized FPT approximation algorithm for sorting unsigned genomes by translocations: breaking the 1.375 approximation barrier
• On the complexity of unsigned translocation distance
• A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations
• Using ciliate operations to construct chromosome phylogenies

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 Q4886096)