On the complexity and approximation of syntenic distance

DOI10.1016/S0166-218X(98)00066-3zbMath0928.68057MaRDI QIDQ1281760

Ming Li, Sampath Kannan, Tao Jiang, Elizabeth Sweedyk, Bhaskar Das Gupta

Publication date: 20 June 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (10)

Fuzzy polynucleotide spaces and metrics ⋮ Topological orderings of weighted directed acyclic graphs ⋮ Optimal algorithms for uncovering synteny problem ⋮ Structural properties and tractability results for linear synteny ⋮ Breakpoint distance and PQ-trees ⋮ An extension of fuzzy topological approach for comparison of genetic sequences ⋮ A metric space to study differences between polynucleotides ⋮ A study of entropy/clarity of genetic sequences using metric spaces and fuzzy sets ⋮ On maximal instances for the original syntenic distance ⋮ Packing of (0, 1)-matrices

Cites Work

• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Genome Rearrangements and Sorting by Reversals
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity and approximation of syntenic distance