On Physical Mapping and the consecutive ones property for sparse matrices

DOI10.1016/S0166-218X(96)00055-8zbMath0876.92011OpenAlexW2056056197MaRDI QIDQ5961616

Martin Middendorf, Jonathan E. Atkins

Publication date: 25 November 1997

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

NP-completefingerprintsmolecular biologyclone libraryphysical mapping problem

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20)

Related Items (7)

Heuristic methods to consecutive block minimization ⋮ The parameterized complexity of stabbing rectangles ⋮ A faster algorithm for finding minimum Tucker submatrices ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ Obtaining matrices with the consecutive ones property by row deletions ⋮ Polynomial-time local-improvement algorithm for consecutive block minimization ⋮ Minimising the number of gap-zeros in binary matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the complexity of DNA physical mapping
• Physical mapping of chromosomes: A combinatorial problem in molecular biology
• Incidence matrices and interval graphs
• Polynomial Complete Consecutive Information Retrieval Problems
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• Interval routing schemes
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques

This page was built for publication: On Physical Mapping and the consecutive ones property for sparse matrices