This is a test version of Biostars. For the public version, visit https://www.biostars.org.
Tool: FastAlign: 3x Faster Sequence Alignment on Commercial CPUs with 100% BWA-MEM Compatibility

Hello everyone,

We are excited to introduce FastAlign, a new open-source sequence alignment tool designed to significantly accelerate genomic data processing on standard commercial CPUs.

As presented at PPoPP '26, FastAlign is designed to break the bottleneck of sequence alignment by optimizing both the seeding and seed-extension phases, offering a faster and cheaper alternative to BWA-MEM and BWA-MEM2 without requiring expensive GPUs or FPGAs.

Key Features & Innovations

  • Drop-in Replacement: FastAlign guarantees 100% identical output to the de facto standard BWA-MEM. You can swap it into your existing pipelines (WGS or WES) without worrying about downstream variant calling discrepancies.
    • Multi-Stage Seeding: We implemented a novel hybrid indexing approach (combining Kmer-Index, FMT-Index, and Direct-Index). This adapts to the sparsity of the genome, achieving an 18.92x improvement in memory efficiency compared to traditional methods.
    • Intra-Query Parallelism: Unlike BWA-MEM2 which uses inter-query parallelism (often leading to load imbalance due to varying read lengths), FastAlign uses an intra-query parallel algorithm with dynamic pruning. This maximizes SIMD utilization (AVX2) regardless of read length distribution.
    • Low Memory Footprint: FastAlign runs efficiently on standard CPUs. It avoids the massive memory consumption often seen in hash-based accelerated aligners (like ERT-BWA-MEM2), making it cost-effective for cloud deployment.

Performance Benchmarks

We evaluated FastAlign against SOTA baselines (BWA-MEM, BWA-MEM2, BWA-GPU, etc.) using human genome datasets (WGS and WES).

  • Throughput: Achieves 2.27x ~ 3.28x speedup compared to BWA-MEM and BWA-MEM2.
  • Cost Efficiency: Delivers a 2.54x ~ 5.65x cost reduction on cloud instances compared to CPU and GPU baselines.
  • Accuracy: 100% match with BWA-MEM output (unlike some GPU heuristics that may drop accuracy).

Availability

FastAlign is open-source and available on GitHub. We welcome feedback, issues, and contributions!

We hope this tool helps speed up your research!

sequece alignment genome analysis
• 3,293 views • link
written by YeWen • YeWen

This looks extremely cool. Especially because I was always a bit underwhelmed that the bwa-mem2 guys, Intel corp after all, kind of traded the impressive speed-up in mem2 with the dramatic increase in memory usage. If you solved both, cudos!

Can you, for personal interest, provide some fairytail talk how this all came to pass, how the project was born and the rough timeline? I always find this super interesting to hear how such things develop.

• 0 views • link
written by ATpoint ATpoint

I can share the slides for this article with you; please refer to this link.

We have utilized BWA-MEM and MEM2 for many years. While they guarantee accuracy, they have consumed excessive computational resources for both our laboratory and the company. Witnessing the success of tools like BWA-MEME and BWA-MEM-ERT gave us the confidence that it was time to construct a more efficient version of BWA-MEM. We believe that our performance gains stem entirely from our deep understanding of the alignment process. We spent approximately six months dissecting the BWA-MEM codebase and another year completing the code optimization. The most grueling part of this process was ensuring 100% accuracy; while this is something many optimization tools fail to achieve, it is a mandatory requirement for a commercial product. Finally, we have submitted this optimized version to a top-tier high-performance computing conference.

• 0 views • link
written by YeWen • YeWen

The most grueling part of this process was ensuring 100% accuracy; while this is something many optimization tools fail to achieve, it is a mandatory requirement for a commercial product

Does it mean that the tool will be commercial (eventually)?

• 0 views • link
written by GenoMax GenoMax

Our software will remain open-source under the MIT license as part of our ongoing research project. As a hardware acceleration provider, our ultimate goal is to deliver comprehensive hardware acceleration services.

• 0 views • link
written by YeWen • YeWen

Thanks! The tool worked perfectly in my testing and the flagstat output is exactly the same. Just one minor detail that it can not use the native bwa index and one needs to index the genome again.

• 0 views • link
written by microfuge microfuge

Thanks for following up. We have to rebuild to create a more efficient hybrid index, and I think the trade-off is worth it~~

• 0 views • link
written by YeWen • YeWen

Can you make a proper release with GitHub that we can package it within bioconda?

• 0 views • link
written by Juke34 Juke34

Providing compiled binaries that people can use right away will also help increase adoption.

• 0 views • link
written by GenoMax GenoMax

Thank you for the suggestion. We will provide the Bioconda package and binaries within a month.

• 0 views • link
written by YeWen • YeWen

Now you can use our tool with bioconda, conda install bioconda::bwa-fastalign, please check it out!

• 0 views • link
written by YeWen • YeWen

I included fastalign into the AliNe nextflow pipeline to compare fast align to other aligner and to original bwa. See here: https://github.com/Juke34/AliNe/tree/fastalign

The thing is I have 33 Segmentation fault for sw and aln only mem works fine. Can you have a look and debug this?

I'm on M2 machine. I have nextflow and docker on my machine and run nextflow run aline.nf -profile docker,test_illumina_single --aligner bwafastalignsw.

• 0 views • link
written by Juke34 Juke34

Requirement from the fastalign repo:

CPU supporting AVX2 instructions (most modern Intel/AMD CPUs).

Juke34 this software is for Intel/AMD CPU's. I am not sure how bwa mem is working on your M* machine. Perhaps that part does not use AVX2.

• 0 views • link
written by GenoMax GenoMax

My bad I thought Rosetta was dealing automatically with it, I thought to just loose the computing speed. I will make a try on another machine. Can you add a fallback when running the tool to inform user if avx2 instruction are available on the machine ? In our HPC we have few nodes not accepting avx2, it would be nice to get a clear message to avoid confusion.

• 0 views • link
written by Juke34 Juke34

I actually checked and the version I was using from bioconda is compiled for ARM machine see here => https://github.com/zzhofict/bioconda-recipes/blob/14d7f5c4204ad559209a2b4db4d14cfeb74105b8/recipes/bwa-fastalign/build.sh

Either it is bugged or it should be not compiled for ARM and distributed...

In the same time I tried to use the tool via Github CI to avoid my ARM machine, again it works for bwafastalignmem but failed with a Segmentation fault for bwafastalignaln...

From what I understand I should not get a Segmentation fault if it was linked to avx2 error instruction but rather Illegal instruction.
@YeWen, for me it sounds like there is an underlying issue in fastalign....

• 0 views • link
written by Juke34 Juke34

Juke34 We only use mem option in our company, so FastAlign only optimize mem function (with 3x speedup and identical output).

• 0 views • link
written by YeWen • YeWen

0 answers

No answers yet.

Log in to answer this question.

More posts like this