Short Read Alignment Based on Maximal Approximate Match Seeds.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Sequence alignment is crucial for genomic studies like variant calling and RNA-seq analysis.
• Repetitive sequences in reference genomes pose significant challenges, leading to computational burdens and potential missed alignments.
• Existing methods often discard repetitive seeds or use maximal exact matches (MEMs) which can fail due to errors.

Purpose of the Study:

• To develop a novel and efficient sequence alignment algorithm capable of handling repetitive genomic sequences.
• To improve the speed and accuracy of short DNA sequence alignment.

Main Methods:

• The proposed algorithm, MAM, utilizes a modified Burrows-Wheeler transform (BWT) for accelerated approximate seed matching.
• It employs maximal approximate matches (MAMs) as seeds to reduce candidate alignment locations.
• Affine-gap-penalty dynamic programming is used to extend these MAM seeds.

Main Results:

• MAM demonstrates superior speed performance compared to state-of-the-art alignment tools.
• Experimental results on simulated and real sequencing data validate the algorithm's effectiveness.
• The algorithm successfully addresses challenges posed by repetitive sequences.

Conclusions:

• MAM offers an efficient solution for sequence alignment, particularly in the presence of repetitive genomic elements.
• The algorithm provides a valuable advancement for genomic research, enhancing speed and potentially accuracy.
• The source code is publicly available for further research and application.