Coal is a sequence alignment tool for long similar reads (produced from the same region). It was developed during my internship in the GenScale team at Inria Rennes.
nw.ccontains a banded version of Needleman-Wunsch algorithmnw_vect.ccontains a vectorized implementation of the same algorithmwidth.cdefines heuristics used for choosing band widthhash.ccontains a simple implementation of a hash table used for storing kmersfasta.ccontains a simple parser for fasta filescoal.ccontains the implementation of the fragmented alignment methodcoal_vect.ccontains a vectorized version of the same methodcoal_standard.ccontains a standard alignment method without fragmentation (used mainly for comparisons)cut.ccontains a tool for sequence preprocessing
This project has no dependencies, so you just have to use make to build the executables.
If your processor supports the AVX2 instruction set, it is recommended to use the vectorized version for better performances: just type make vect.
Also note that you need to have gcc in order to compile AVX instructions (on macOS make sure that the CC variable in the Makefile refers to the actual gcc compiler - not clang).
If you want to change specific parameters of the algorithm such as the size of kmers, have a look at the Makefile to see the different flags you can set for compilation.
Once coal is built, you just have to run ./coal <seq1.fasta> <seq2.fasta> to align two sequences.
The same applies to coal_vect and coal_standard.
You can find some test sequences in the examples directory.
This repository also provides a tool named cut which can be used to preprocess a pair of sequences:
./cut <seq1.fasta> <seq2.fasta> <out1> <out2>.
What cut does is that it cuts (sic) the given sequences between their first and their last anchor points.
This might be useful if the sequences have an important offset.
- provide a complete CLI instead of obscure compilation flags
- provide a vectorized version of Gotoh's algorithm as an alternative to Needleman-Wunsch
- make it easier to use an external library for the alignment of subsequences (instead of
nw.h) - improve the hashing method (e.g. by using Robin Hood Hashing or Cuckoo Hashing)
- extend vectorization for bigger band width (32, 64, or even an arbitrary width)
- refine the choice of kmers used as anchor points
This project is licensed under the MIT License. Any code contribution intentionally made to the project in this repository must be licensed under the same license.