#compression #plain-text #kmer #genome #bio

bin+lib matchtigs

Different algorithms for computing small and minimum plain text representations of kmer sets

15 stable releases

1.7.0 May 2, 2023
1.6.0 May 2, 2023
1.5.5 Dec 8, 2022
1.5.3 Nov 17, 2022
1.0.0 Dec 2, 2021

#52 in Compression

Download history 17/week @ 2023-02-06 40/week @ 2023-02-13 22/week @ 2023-02-20 12/week @ 2023-02-27 12/week @ 2023-03-06 12/week @ 2023-03-13 6/week @ 2023-03-20 35/week @ 2023-03-27 1/week @ 2023-04-03 28/week @ 2023-04-10 39/week @ 2023-04-17 10/week @ 2023-04-24 42/week @ 2023-05-01 37/week @ 2023-05-08 13/week @ 2023-05-15 18/week @ 2023-05-22

111 downloads per month

Custom license

3.5K SLoC

Matchtigs & Eulertigs: minimum plain text representation of kmer sets - with and without repetitions

Version Downloads Docs

Anaconda-Server Badge Anaconda-Server Badge

This is an implementation of different algorithms for computing small and minimum plain text representations of kmer sets. The algorithms expect unitigs as an input, which can e.g. be computed with GGCAT or BCALM2.

If you wish to compute matchtigs or Eulertigs from arbitrary input without computing unitigs yourself first, consider using GGCAT. Its readme mentions the required flags.


  • Compute matchtigs and greedy matchtigs with multiple threads
  • Compute Eulertigs
  • Compute pathtigs (heuristical Eulertigs similar to ProphAsm)
  • Both fasta and GFA format supported, as well as gzip compression if the files end in .gz
  • The annotations in a fasta file output by GGCAT (use -e flag) or BCALM2 (no flag required) can be used to speed up loading (use --bcalm-in instead of --fasta-in)
  • Output (ASCII-) bitvectors of duplicate kmers for applications that require unique kmers


The matchtigs tool can be installed with the following methods. Out of the box, it implements all algorithms but the optimal matchtig algorithm. This is because the optimal matchtig algorithm uses the commercial software blossom V, which is freely available for researchers, but cannot be publicly redistributed. For all practical purposes, we recommend using greedy matchtigs, as they are a lot more efficient to compute, and have very similar cumulative length and string count as matchtigs (see the matchtigs publication linked below).

Installation via conda/mamba

Install matchtigs with

mamba install -c conda-forge -c bioconda matchtigs

Installation via cargo


Rust >= 1.64.0, best installed via rustup.


Install matchtigs with

cargo install matchtigs


Computing matchtigs and greedy matchtigs from a fasta file and saving them as GFA (without topology):

matchtigs --fa-in unitigs.fa --matchtigs-gfa-out matchtigs.gfa --greedytigs-gfa-out greedy-matchtigs.gfa

Computing Eulertigs from a GFA file and saving them as both GFA (without topology) and fasta:

matchtigs --fa-in unitigs.fa --eulertigs-gfa-out eulertigs.gfa --eulertigs-fa-out eulertigs.fa

Note: when computing unitigs with GGCAT or BCALM2, it is much faster to use --bcalm-in:

matchtigs --bcalm-in unitigs.fa --eulertigs-gfa-out eulertigs.gfa --eulertigs-fa-out eulertigs.fa

Use the --help option to get an overview of available options.

matchtigs --help


matchtigs preprint

Schmidt, S., Khan, S., Alanko, J., & Tomescu, A. I. (2021). Matchtigs: minimum plain text representation of kmer sets. bioRxiv. https://doi.org/10.1101/2021.12.15.472871.

Eulertigs (WABI 2022 best paper award)

Schmidt, S. and Alanko, J. (2022). Eulertigs: minimum plain text representation of k-mer sets without repetitions in linear time. WABI 2022. 10.4230/LIPIcs.WABI.2022.2.


~417K SLoC