Title

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.

Comments

Algorithms in Bioinformatics: 8th International Workshop, WABI 2008 (September 2008): 148-161. DOI.