FMTP

FMTP computes the Minimum Tiling Path (MTP) from restriction fingerprint data and contig information derived from physical maps to select a minimal set of clones that cover a genome with minimal redundancy for hierarchical genome sequencing projects.

Key Features:

• Input data: Operates on restriction fingerprint data and contig information from physical maps.
• Graph theoretical framework: Formulates the MTP problem within a graph-theoretical context representing clones and overlaps.
• Algorithmic approach: Employs minimum hitting set and minimum spanning tree algorithms to determine an optimal tiling path.
• Performance comparison: Produces MTPs that cover a larger portion of the genome using fewer clones compared to FPC (Fingerprinted Contigs).
• Cost efficiency: Application to the rice genome indicates an approximate 11% reduction in sequencing project costs due to decreased clone usage.

Scientific Applications:

• Hierarchical genome sequencing: Selects clone sets for clone-by-clone hierarchical genome sequencing projects to assemble genomes from overlapping clones.
• Physical-map-based assembly planning: Generates MTPs from physical maps to guide sequencing and resource allocation in large-scale genomics efforts.
• Cost optimization: Reduces clone redundancy and resource requirements to lower sequencing costs, as exemplified by the rice genome analysis.

Methodology:

Represents the physical map as a graph and identifies a minimum set of nodes (clones) that cover all edges using minimum hitting set and minimum spanning tree algorithms.