FastGA: fast genome alignment.

ABSTRACT:

Motivation

FastGA finds alignments between two genome sequences more than an order of magnitude faster than previous methods that have comparable sensitivity. Its speed is due to (i) a fully cache-local architecture involving only MSD radix sorts and merges, (ii) an algorithm for finding adaptive seed hits in a linear merge of sorted k-mer tables, and (iii) a variant of the Myers adaptive wave algorithm to find alignments around a chain of seed hits. It further stores alignments in a fraction of the space of a conventional CIGAR string using a trace-point encoding and our ONEcode data system introduced here.

Results

For example, two 2 Gbp bat genomes are compared in 2.1 min with eight threads on an Apple laptop using 5.7 GB of memory and pr

SUBMITTER: Myers G 

PROVIDER: S-EPMC12624442 | biostudies-literature | 2025

REPOSITORIES: biostudies-literature