KegAlign: Optimizing pairwise alignments with diagonal partitioning.

Area of Science:

• Genomics
• Computational Biology
• Bioinformatics

Background:

• Advances in genome sequencing generate vast amounts of data, necessitating efficient tools for analysis.
• Multiple genome alignment is crucial for understanding organismal biology and evolution but is computationally intensive.
• The generation of accurate pairwise alignments between divergent genomes is a major bottleneck in creating multiple alignments.

Purpose of the Study:

• To develop an optimized, GPU-enabled pairwise aligner to accelerate the process of comparing divergent genomes.
• To overcome the computational limitations of existing tools like lastZ for large-scale genome alignment.
• To provide a sensitive and efficient tool for genomic research that can be readily adopted.

Main Methods:

• Developed KegAlign, a GPU-enabled pairwise sequence aligner utilizing diagonal partitioning for parallelization.
• Leveraged modern Graphics Processing Unit (GPU) features for enhanced computational performance.
• Integrated KegAlign with a Galaxy workflow for user accessibility and ease of use.

Main Results:

• KegAlign achieved a ~150x speed improvement over lastZ for human/mouse genome alignment.
• A typical human/mouse alignment was completed in under 6 hours on a single NVidia A100 GPU with 80 CPU cores.
• KegAlign maintains the high sensitivity of lastZ, crucial for comparing divergent genomes, unlike faster but less sensitive alternatives.

Conclusions:

• KegAlign effectively addresses the computational bottleneck in pairwise genome alignment, significantly accelerating genomic research.
• The tool's high sensitivity and speed make it suitable for comparing divergent genomes, advancing evolutionary and biological studies.
• Availability of source code, a Conda package, and a Galaxy workflow promotes widespread adoption and utilization in the scientific community.