Computing the Minimal Tiling Path from a Physical Map by Integer Linear Programming
Document Type
Article
Language
eng
Format of Original
14 p.
Publication Date
9-2008
Publisher
Springer
Source Publication
Algorithms in Bioinformatics: 8th International Workshop, WABI 2008
Source ISSN
9783540873617
Original Item ID
doi: 10.1007/978-3-540-87361-7_13
Abstract
We study the problem of selecting the minimal tiling path (MTP) from a set of clones arranged in a physical map. We formulate the constraints of the MTP problem in a graph theoretical framework, and we derive an optimization problem that is solved via integer linear programming. Experimental results show that when we compare our algorithm to the commonly used software FPC, the MTP produced by our method covers a higher portion of the genome, even using a smaller number of MTP clones. These results suggest that if one would employ the MTP produced by our method instead of FPC’s in a clone-by-clone sequencing project, one would reduce by about 12% the sequencing cost.
Recommended Citation
Bozdag, Serdar; Close, Timothy J.; and Lonardi, Stefano, "Computing the Minimal Tiling Path from a Physical Map by Integer Linear Programming" (2008). Mathematics, Statistics and Computer Science Faculty Research and Publications. 69.
https://epublications.marquette.edu/mscs_fac/69
Comments
Algorithms in Bioinformatics: 8th International Workshop, WABI 2008 (September 2008): 148-161. DOI.