Large scale sequence alignment via efficient inference in generative models.

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Sequence alignment is vital for analyzing genomic data.
• Existing heuristic algorithms are fast but lack sensitivity for complex sequence variations.
• High error rates in sequencing reads challenge accurate alignment.

Purpose of the Study:

• To develop a theoretically principled and efficient sequence alignment algorithm.
• To achieve high sensitivity across diverse insertion, deletion, and mutation rates.
• To improve the accuracy of aligning long sequencing reads to genome sequences.

Main Methods:

• Framing sequence alignment as a probabilistic inference problem.
• Maximizing the log-likelihood ratio between joint and independent probabilistic models.
• Implementing a bucketing strategy to group high-likelihood read alignments.

Main Results:

• The new algorithm demonstrates high sensitivity for reads with various error profiles.
• It significantly outperforms existing state-of-the-art methods in accuracy.
• Experimental validation shows superior performance in aligning long reads from Pacific Biosciences sequencers.

Conclusions:

• The developed algorithm offers a theoretically sound and efficient approach to sequence alignment.
• It provides a more sensitive and accurate solution compared to current heuristic methods.
• This advancement is particularly beneficial for analyzing challenging long-read sequencing data.