Inexact Local Alignment Search over Suffix Arrays

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Traditional DNA homology search algorithms rely on exact or spaced seeds, limiting their ability to detect evolutionary relationships accurately.
• The presence of insertions and deletions in DNA sequences poses a significant challenge for existing homology search methods.
• Efficiently finding and utilizing seeds that account for sequence variations is crucial for improving alignment sensitivity and speed.

Purpose of the Study:

• To develop and present a novel algorithm for DNA homology searches that incorporates approximate seeds capable of handling insertions and deletions.
• To demonstrate the efficiency and sensitivity of the proposed heuristic for finding approximate seeds.
• To adapt the algorithm for use with memory-efficient suffix arrays with minimal performance overhead.

Main Methods:

• Developed a generalized heuristic algorithm for efficiently finding approximate seeds in DNA sequences, allowing for insertions and deletions.
• Proved that the heuristic approach does not compromise the sensitivity of homology detection.
• Adapted the algorithm to operate on memory-efficient suffix arrays, ensuring minimal impact on running time.
• Applied the algorithm to whole bacterial genome alignment and orthologous gene alignment between human and mouse.

Main Results:

• The algorithm successfully identified approximate seeds, accommodating insertions and deletions, thereby improving homology detection.
• The heuristic was proven to maintain or enhance alignment sensitivity.
• Adaptation to suffix arrays resulted in minimal overhead in running time while optimizing memory efficiency.
• Demonstrated superior sensitivity and reduced memory consumption compared to commonly used local alignment tools in bacterial genome and cross-species gene alignment tasks.

Conclusions:

• The developed algorithm offers a more sensitive and memory-efficient approach to DNA homology searches by utilizing approximate seeds.
• This method represents a significant advancement for comparative genomics, particularly for tasks involving sequence variation.
• The algorithm's adaptability to suffix arrays makes it a practical tool for large-scale genomic analyses.