Document Type
Article
Language
eng
Format of Original
9 p.
Publication Date
3-2013
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Source Publication
IEEE/ACM Transactions on Computational Biology and Bioinformatics
Source ISSN
1545-5963
Original Item ID
doi: 10.1109/TCBB.2013.26
Abstract
The problem of computing the minimum tiling path (MTP) from a set of clones arranged in a physical map is a cornerstone of hierarchical (clone-by-clone) genome sequencing projects. We formulate this problem in a graph theoretical framework, and then solve by a combination of minimum hitting set and minimum spanning tree algorithms. The tool implementing this strategy, called FMTP, shows improved performance compared to the widely used software FPC. When we execute FMTP and FPC on the same physical map, the MTP produced by FMTP covers a higher portion of the genome, and uses a smaller number of clones. For instance, on the rice genome the MTP produced by our tool would reduce by about 11 percent the cost of a clone-by-clone sequencing project. Source code, benchmark data sets, and documentation of FMTP are freely available at >http://code.google.com/p/fingerprint-based-minimal-tiling-path/ under MIT license.
Recommended Citation
Bozdag, Serdar, "A Graph-Theoretical Approach to the Selection of the Minimum Tiling Path from a Physical Map" (2013). Mathematics, Statistics and Computer Science Faculty Research and Publications. 104.
https://epublications.marquette.edu/mscs_fac/104
Comments
Accepted version. IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 10, No. 2 (March 2013): 352-360. DOI. © 2013 Institute of Electrical and Electronics Engineers (IEEE) . Used with permission.