A Branch-and-Cut Approach to Physical Mapping of Chromosomes by Unique End-Probes
- 1 January 1997
- journal article
- research article
- Published by Mary Ann Liebert Inc in Journal of Computational Biology
- Vol. 4 (4), 433-447
- https://doi.org/10.1089/cmb.1997.4.433
Abstract
A fundamental problem in computational biology is the construction of physical maps of chromosomes from hybridization experiments between unique probes and clones of chromosome fragments in the presence of error. Alizadeh, Karp, Weisser and Zweig (Algorithmica 13:1/2, 52–76, 1995) first considered a maximum-likelihood model of the problem that is equivalent to finding an ordering of the probes that minimizes a weighted sum of errors and developed several effective heuristics. We show that by exploiting information about the end-probes of clones, this model can be formulated as a Weighted Betweenness Problem. This affords the significant advantage of allowing the well-developed tools of integer linear-programming and branch-and-cut algorithms to be brought to bear on physical mapping, enabling us for the first time to solve small mapping instances to optimality even in the presence of high error. We also show that by combining the optimal solution of many small overlapping Betweenness Problems, one can effectively screen errors from larger instances and solve the edited instance to optimality as a Hamming-Distance Traveling Salesman Problem. This suggests a new approach, a Betweenness-Traveling Salesman hybrid, for constructing physical maps. Key words: computational biology, physical mapping of chromosomes, betweenness problem, linear ordering problem, branch-and-cutKeywords
This publication has 11 references indexed in Scilit:
- Combinatorial optimization and small polytopesTOP, 1996
- Physical mapping of chromosomes: A combinatorial problem in molecular biologyAlgorithmica, 1995
- A Note on Scoring Clones Given a Probe OrderingJournal of Computational Biology, 1995
- Fragment Collapsing and Splitting While Assembling High-Resolution Restriction MapsJournal of Computational Biology, 1995
- Physical Mapping by STS Hybridization: Algorithmic Strategies and the Challenge of Software EvaluationJournal of Computational Biology, 1995
- An Algorithm to Detect Chimeric Clones and Random Noise in Genomic MappingGenomics, 1994
- Algorithms and software tools for ordering clone libraries: application to the mapping of the genome ofSchizosaccharomyces pombeNucleic Acids Research, 1993
- Facets of the linear ordering polytopeMathematical Programming, 1985
- A Cutting Plane Algorithm for the Linear Ordering ProblemOperations Research, 1984
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976