Aligning distant sequences to graphs using long seed sketches.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Sequence-to-graph alignment is essential for key genomic tasks, including variant genotyping, read error correction, and genome assembly.
• Current methods often struggle with high mutation rates and large graph sizes, impacting efficiency and accuracy.

Purpose of the Study:

• To develop a novel seeding approach for sequence-to-graph alignment that enhances the time-accuracy trade-off.
• To improve the robustness of alignment methods against indels and high mutation rates.
• To demonstrate the scalability and efficiency of the proposed method for large genomic graphs.

Main Methods:

• A new seeding strategy based on long inexact matches instead of short exact matches.
• Utilizing sketches of graph nodes for increased robustness to insertions and deletions (indels).
• Employing a k-nearest neighbor index to manage high-dimensional data and avoid the curse of dimensionality.

Main Results:

• The proposed method achieves a superior time-accuracy trade-off for mutation rates up to [Formula: see text].
• The sketching approach demonstrates robustness against indels.
• The method scales to graphs with 1 billion nodes, offering quasi-logarithmic query time for specific edit distances.
• Sketch-based seeds provide a [Formula: see text] increase in recall compared to exact seeds for queries with a [Formula: see text] edit distance.

Conclusions:

• The novel seeding approach offers significant improvements in sequence-to-graph alignment efficiency and accuracy.
• Sketching into vector space is a valuable technique for bioinformatics applications.
• This method provides a scalable and robust solution for aligning sequences to large graphs, applicable to various genomic analyses.