clasp

clasp chains short local match fragments to improve sensitivity and specificity of sequence alignment for comparative genomics of large mammalian genomes.

Key Features:

• Support for Linear and Sum-of-Pair Gap Costs: clasp implements both linear and sum-of-pair gap cost models, with the sum-of-pair model enabling higher sensitivity for precise homology detection.
• Highly Time-Efficient Index Structure: clasp uses Johnson priority queues and range trees padded with Johnson priority queues for indexing, enabling rapid processing of alignment fragments and outperforming tools limited to the linear gap cost model.
• Integration with Existing Alignment Tools: clasp accepts and chains short match fragments generated by alignment tools such as segemehl and BLAST to enhance detection of homologous regions.

Scientific Applications:

• Comparative Genomics: clasp aids identification of synteny and homologous regions among proteins, genes, and non-coding RNAs across species such as human and mouse.
• Homology-Based Searches: clasp improves sensitive detection of small nucleolar RNAs (snoRNAs) and other homologs that may be missed by standard local alignment heuristics.

Methodology:

clasp connects, scores, and ranks short match fragments generated from initial alignments; it supports linear and sum-of-pair gap cost models and uses Johnson priority queues and range trees padded with Johnson priority queues for indexing.