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 sequences via colinear chaining in O(n log n) time, built on the same tech stack as at-cg/ChainX. It supports FASTA or gzipped FASTA input, it computes maximal unique/exact anchors, and it supports the output of an optimal chain in MUMmer-like or SAM format.

Right now, the program has been tested with GCC version 15. Get the repository and compile llchain with

git clone https://github.com/nrizzo/llchain && cd llchain
git submodule update --init ext/mummer
make -j $(nproc)
./llchain --text test/T1.fasta --query test/T2.fasta

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:

• kseq for FASTA parsing
• mummer (essaMEM) for seed finding
• algbio/ChainX for the --chainx and --chainx-opt flags
• grid_to_bmp for debugging

Dependencies

gengetopt for development

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

• use CLI11 instead of gengetopt
• clang
• investigate sorting
• investigate predecessor data structures
• avoid using a list in case 3