Structural properties and tractability results for linear synteny

DOI10.1016/S1570-8667(03)00081-9zbMATH Open1114.92050OpenAlexW2061735186MaRDI QIDQ876715FDOQ876715

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

comparative genomicsscheduling problemsgenome rearrangementssynthetic distance

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Title not available (Why is that?)
• Further thoughts on the syntenic distance between genomes

   Recommendations

• Title not available (Why is that?) 👍 👎
• Structural and Complexity Aspects of Line Systems of Graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• On the structure of linear graphs 👍 👎
• On the structure of linear graphs 👍 👎
• Linear \(k\)-arboricities on trees 👍 👎
• Towards the linear arboricity conjecture 👍 👎
• Optimal algorithms for uncovering synteny problem 👍 👎

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

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