llchain — log-linear chaining with L∞ gap costs and Δdiag overlap costs

llchain is a C++20 program to compute the anchored edit distance between query and reference DNA sequences in O(n log n) time, where n is the number of input anchors (currently MUMs or MEMs). The program is built on the same tech stack as at-cg/ChainX, it supports (gzipped) FASTA input, computes maximal unique/exact anchors, and can output the optimal chains in MUMmer-like, SAM, or PAF format.

Right now, llchain has been only tested with GCC versions 15 and 16. Get the repository, compile the HTSlib dependency, and build llchain with commands

git clone https://github.com/nrizzo/llchain && cd llchain
git submodule update --init ext/mummer ext/CLI11 ext/concurrentqueue
(git submodule update --init --recursive ext/htslib && cd ext/htslib && autoreconf -i && ./configure && make -j$(nproc)) # if HTSlib + headers are not installed in your system
make -j $(nproc)
./llchain --text test/T1.fasta --query test/T2.fasta --sam test/out.sam | column -t
./llchain --all-to-all --text test/Q.fasta --phylip test/out.phylip | column -t

Experiments

To run the experiment on HG002 PacBio HiFi reads aligned to the T2T-CHM13 reference, check experiments/ChainX-human/README.md. The results, where we compare the chaining cost of llchain to ChainX and ChainX-opt on maximal exact match anchors of length >= 50, are shown in the next figure.

External libraries

llchain is built with the following libraries:

• HTSlib and kseq for FASTA parsing
• mummer (essaMEM) for seed finding
• algbio/ChainX for the --chainx and --chainx-opt flags
• moodycamel::ConcurrentQueue for handling multithreading queues
• grid_to_bmp for debugging

Citation

If you use flags --chainx or --chainx-opt, please cite the corresponding works:

• Chirag Jain, Daniel Gibney and Sharma Thankachan. "Algorithms for Colinear Chaining with Overlaps and Gap Costs". Journal of Computational Biology, 2022.
• Nicola Rizzo, Manuel Cáceres, and Veli Mäkinen. "Practical colinear chaining on sequences revisited" (arXiv). ISBRA 2025.

TODOs

• PAF input
• clang
• investigate sorting
• investigate predecessor data structures
• avoid using a list in case 3