Faculty Collaboration Database

A graph-theoretical approach to the selection of the minimum tiling path from a physical map. IEEE/ACM Trans Comput Biol Bioinform 2013;10(2):352-60

Date

08/10/2013

Pubmed ID

23929859

DOI

10.1109/TCBB.2013.26

Scopus ID

2-s2.0-84883015012 (requires institutional sign-in at Scopus site)   5 Citations

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.

Author List

Bozdag S, Close TJ, Lonardi S

Author

Serdar Bozdag BS,PhD Assistant Professor, Director of Bioinformatics Lab in the Dept. of Mathematics, Statistics and Computer Science department at Marquette University

MESH terms used to index this publication - Major topics in bold

Algorithms
Chromosome Mapping
Genome, Plant
Genomics
Hordeum
Internet
Oryza
Sequence Analysis, DNA
Software