Fast local fragment chaining using sum-of-pair gap costs

Area of Science:

• Bioinformatics
• Comparative Genomics
• Computational Biology

Background:

• Fast seed-based alignment heuristics (e.g., BLAST, BLAT) are crucial for comparative genomics, especially for large mammalian genomes.
• Alignment sensitivity and specificity depend on parameters like seed size and expectation values.
• High-sensitivity searches generate numerous short local match fragments, necessitating efficient processing.

Purpose of the Study:

• To present a fast and flexible fragment chainer for connecting and scoring local alignment fragments.
• To introduce and implement a sum-of-pair gap cost model for fragment chaining, enhancing accuracy and sensitivity.
• To provide a tool that outperforms existing methods for fragment chaining.

Main Methods:

• Developed a novel fragment chainer with a time-efficient index structure.
• Implemented support for both linear and sum-of-pair gap cost models.
• Applied the fragment chainer to outputs from alignment tools like segemehl and BLAST.

Main Results:

• The new fragment chainer outperforms existing tools under the linear gap cost model.
• The sum-of-pair gap cost model demonstrates substantial advantages in accuracy and sensitivity.
• Demonstrated the utility in homology-based searches for human and mouse snoRNAs using BLAST and chaining.

Conclusions:

• Fragment chaining effectively identifies homologous regions missed by local alignment heuristics alone.
• The inclusion of both linear and sum-of-pair gap cost models broadens the tool's applicability.
• The software 'clasp' is available for researchers to utilize these advanced fragment chaining capabilities.