MaxSSmap: a GPU program for mapping divergent short reads to genomes with the maximum scoring subsequence.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Traditional genome mapping tools (hash tables, Burrows-Wheeler) are fast but lack accuracy with sequence variations like mismatches and gaps.
• Accurate alignment algorithms like Smith-Waterman are slow, requiring days for large datasets, hindering efficient genomic analysis.

Purpose of the Study:

• To develop a GPU-accelerated program, MaxSSmap, for high-accuracy genome read mapping.
• To achieve Smith-Waterman level accuracy with significantly reduced computational runtime.

Main Methods:

• MaxSSmap employs a GPU-based approach to calculate maximum scoring subsequence scores between reads and disjoint genome fragments in parallel.
• The highest scoring fragment is selected for precise, exact alignment, bypassing traditional hash table or Burrows-Wheeler methods for initial read localization.

Main Results:

• MaxSSmap demonstrates accuracy comparable to Smith-Waterman with substantially lower runtimes across simulated and real genomic datasets.
• The program effectively maps reads with 10-30% mismatches and gaps, including those rejected by BWA and NextGenMap.
• Evaluations on E.coli and human chromosome one reads, as well as ancient DNA and NA12878 data, confirm MaxSSmap's performance.

Conclusions:

• MaxSSmap provides a highly accurate and efficient solution for genome read mapping, especially for challenging sequences with variations.
• The tool significantly outperforms existing methods like BWA and NextGenMap in accuracy and speed for specific mapping tasks.
• MaxSSmap's source code is publicly available, facilitating further research and application in bioinformatics.