GRAM and genfragII: solving and testing the single-digest, partially ordered restriction map problem

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Genome mapping relies on analyzing restriction fragments from overlapping clones.
• Experimental data in restriction mapping often contains errors and uncertainties, complicating computational analysis.
• Existing methods face challenges in accurately assembling restriction maps from complex datasets.

Purpose of the Study:

• To develop an efficient computational tool, GRAM, for assembling partially ordered restriction maps.
• To facilitate collaborative problem-solving between humans and machines in genomic restriction mapping.
• To provide a user-interactive system for querying and editing generated restriction maps.

Main Methods:

• GRAM employs a clustering algorithm to identify probable sets of restriction fragments.
• A stochastic assembly algorithm is used to order fragments, maximizing contiguity.
• Interactive graphics are integrated to support user-guided map refinement and editing.

Main Results:

• GRAM generates plausible, partially ordered restriction maps with corresponding clone fragment alignments.
• The system effectively approximates solutions for computationally challenging restriction mapping problems.
• Performance was validated using genfragII, a simulation program for clone digestion.

Conclusions:

• GRAM provides a robust framework for genomic restriction map assembly.
• The man-machine collaborative approach enhances the accuracy and efficiency of genome mapping.
• GRAM is actively utilized in ongoing genome mapping projects, demonstrating its practical utility.