Structural properties and tractability results for linear synteny

DOI10.1016/S1570-8667(03)00081-9zbMath1114.92050OpenAlexW2061735186MaRDI QIDQ876715

David Liben-Nowell, Jon M. Kleinberg

Publication date: 26 April 2007

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s1570-8667(03)00081-9

zbMATH Keywords

scheduling problemscomparative genomicsgenome rearrangementssynthetic distance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15) Protein sequences, DNA sequences (92D20) Operations research and management science (90B99)

Cites Work

• Unnamed Item
• Unnamed Item
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• On the complexity and approximation of syntenic distance
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Transforming cabbage into turnip
• Scheduling to Minimize Maximum Cumulative Cost Subject to Series-Parallel Precedence Constraints
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sorting by Transpositions
• (1+ε)-Approximation of Sorting by Reversals and Transpositions
• Genome Rearrangements and Sorting by Reversals
• Sorting a bridge hand
• Conserved synteny as a measure of genomic distance

This page was built for publication: Structural properties and tractability results for linear synteny