The R package edlibR provides bindings to edlib, a performant C/C++
library for calculating the exact pairwise sequence alignment using the
edit distance
(Levenshtein
distance). The package is modeled after the API of the Python package edlib.
The original Python bindings to the C/C++ library using Cython can be found here. Much of the background information below is directly from the original README for edlib.
For details and examples of the edlibR functionality, see the vignettes: * HTML version * Markdown version
There are three functions within edlibR:
align()
align(query, target, [mode], [task], [k], [cigarFormat], [additionalEqualities])getNiceAlignment()
getNiceAlignment(alignResult, query, target, [gapSymbol])nice_print()
nice_print(niceAlignment)Edlib supports three alignment methods: * global
(NW) - This is the standard method, when we say “edit distance”
this is the method that is assumed. (Note that ‘NW’ stands for
‘Needleman-Wunsch’.) It tells us the smallest number of operations
needed to transform the first sequence into the second sequence.
This method is appropriate when you want to find out how similar the
first sequence is to the second sequence. * prefix
(SHW) - Similar to the global method, but with a small twist -
the gap at the query end is not penalized. What this means is that
deleting elements from the end of the second sequence is “free”! (Note
that ‘HW’ stands for ‘Hybrid Wunsch’.) For example, if we had query as
AACT and target as AACTGGC, the edit distance
would be 0, because removing GGC from the end of the second
sequence is “free” and does not count into the total edit distance.
This method is appropriate when you want to find out how well the
first sequence fits at the beginning of the second sequence. *
infix (HW): Similar as prefix method, but with one more
twist - gaps at query end and start are not penalized.
What this means is that deleting elements from both the start and the
end of the second sequence is “free”! (Note that ‘SHW’ stands for
‘Semi-Hybrid Wunsch’.) For example, if we had query as ACT
and target as CGACTGAC, the edit distance would be 0,
because removing CG from the start and GAC
from the end of the second sequence is “free” and does not count into
the total edit distance. This method is appropriate when you want to
find out how well the first sequence fits at any part of the second
sequence. For example, if your second sequence was a long text and
your first sequence was a sentence from that text, but slightly
scrambled, you could use this method to discover how scrambled it is and
where it fits in that text. In bioinformatics, this method is
appropriate for aligning a read to a sequence.
Edlib is based on Myers’s bit-vector algorithm[1] and extends from it.
It calculates a dynamic programming matrix of dimensions
Q x T, where Q is the length of the first
sequence (query), and T is the length of the second
sequence (target). It uses Ukkonen’s banded algorithm[2] to reduce the space of search, and there is also
parallelization from Myers’s algorithm, however time complexity is still
quadratic.
Edlib uses Hirschberg’s algorithm[3] to find the alignment path, therefore space complexity is linear.
More details can be found within the edlib publication[4].
To install the stable version from CRAN, use:
install.packages('edlibR')To install the latest version, use:
install.packages('devtools')
devtools::install_github('evanbiederstedt/edlibR')The R package can be cited as follows:
Martin Šošić and Evan Biederstedt (2022). edlibR: R wrapper to edlib,
the C/C++ library for fast exact sequence alignment using edit
(Levenshtein) distance. R package version 1.0.0.
https://github.com/evanbiederstedt/edlibRPlease also cite the original edlib publication, which can be found here and should be cited as follows:
Martin Šošić, Mile Šikić (2017). Edlib: a C/C++ library for fast, exact sequence alignment using edit distance.
Bioinformatics, Volume 33, Issue 9, 1 May 2017, Pages 1394–1395,
https://doi.org/10.1093/bioinformatics/btw753[1] Myers G. (1999) A fast bit-vector algorithm for approximate string matching based on dynamic programming. J. ACM, 46, 395–415. https://doi.org/10.1145/316542.316550
[2] Ukkonen E. (1985) Algorithms for approximate string matching. Inform. Control, 64, 100–118. https://doi.org/10.1016/S0019-9958(85)80046-2
[3] Hirschberg D.S. (1975) A linear space algorithm for computing maximal common subsequences. Commun. ACM, 18, 341–343. https://doi.org/10.1145/360825.360861
[4] Martin Šošić, Mile Šikić. Edlib: a C/C++ library for fast, exact sequence alignment using edit distance, Bioinformatics, Volume 33, Issue 9, 1 May 2017, Pages 1394–1395, https://doi.org/10.1093/bioinformatics/btw753