A fast adaptive algorithm for computing whole-genome homology maps.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Whole-genome alignment is crucial for comparative genomics, genome assembly mapping, and repeat identification.
• Large-scale plant and animal genomes present significant computational and memory challenges for alignment.
• Existing alignment methods lack guarantees on output characteristics, hindering optimization for specific applications.

Purpose of the Study:

• To introduce an approximate algorithm for computing local alignment boundaries in long DNA sequences.
• To provide probabilistic guarantees on alignment sensitivity and enable tuning for diverse application needs.
• To develop a theoretically optimal and practically efficient filtering technique for prioritizing high-scoring alignment intervals.

Main Methods:

• An approximate algorithm utilizing k-mer based statistics for local alignment boundary computation.
• A plane-sweep based filtering technique to prioritize higher scoring alignment intervals.
• Implementation as a fast and accurate assembly-to-genome and genome-to-genome mapper.

Main Results:

• Achieved whole-genome mapping of a human assembly to a reference genome in ~1 minute with <4 GB memory.
• Demonstrated >97% recall accuracy for computed alignment boundaries across multiple datasets.
• Identified human genome duplications (≥1 Kbp, ≥90% identity) with good recall, covering twice the bases of current annotations.

Conclusions:

• The developed algorithm offers a significant improvement in memory usage and execution time for whole-genome alignment.
• The method provides reliable alignment boundary detection with high accuracy.
• Enables sensitive detection of genomic duplications, enhancing our understanding of genome structure and evolution.