Description
A collection of Radix Tree and Trie algorithms for finding similar sequences and calculating sequence distances (Levenshtein and other distance metrics). This work was inspired by a trie implementation in Python: "Fast and Easy Levenshtein distance using a Trie." Hanov (2011) <https://stevehanov.ca/blog/index.php?id=114>. It also includes a modified version of the Starcode all-pairs search algorithm (Zorita, Cuscó, and Filion 2015) <doi:10.1093/bioinformatics/btv053>.
Downloads
164
Last 30 days
16231st
653
Last 90 days
2.6K
Last year
Trend: -24.1% (30d vs prior 30d)
CRAN Check Status
Show all 13 flavors
| Flavor | Status |
|---|---|
| r-devel-linux-x86_64-debian-clang | OK |
| r-devel-linux-x86_64-debian-gcc | OK |
| r-devel-linux-x86_64-fedora-clang | OK |
| r-devel-linux-x86_64-fedora-gcc | OK |
| r-devel-windows-x86_64 | OK |
| r-oldrel-macos-arm64 | OK |
| r-oldrel-macos-x86_64 | ERROR |
| r-oldrel-windows-x86_64 | OK |
| r-patched-linux-x86_64 | OK |
| r-release-linux-x86_64 | OK |
| r-release-macos-arm64 | OK |
| r-release-macos-x86_64 | OK |
| r-release-windows-x86_64 | OK |
Check details (1 non-OK)
tests
Running ‘test_RadixForest.R’ [4s/5s]
Running ‘test_RadixTree.R’ [11s/11s]
Running ‘test_StarTree.R’ [71s/58s]
Running ‘test_pairwise.R’ [4s/5s]
Running the tests in ‘tests/test_pairwise.R’ failed.
Complete output:
> # This test file tests the `dist_matrix` and `dist_pairwise` functions
> # These two functions are simple dynamic programming algorithms for computing pairwise distances and are themselves used to validate
> # the RadixTree imeplementation (see test_radix_tree.R)
>
> runtime <- Sys.time()
>
> if(requireNamespace("seqtrie", quietly=TRUE) &&
+ requireNamespace("pwalign", quietly=TRUE)
+ ) {
+ library(seqtrie)
+ library(pwalign)
+
+ # Use 2 threads on github actions and CRAN, 4 threads locally
+ IS_LOCAL <- Sys.getenv("IS_LOCAL") != ""
+ NTHREADS <- ifelse(IS_LOCAL, 4, 2)
+ NITER <- ifelse(IS_LOCAL, 3, 1)
+ NSEQS <- 2500
+ MAXSEQLEN <- 200
+ CHARSET <- "ACGT"
+
+ test_seed <- Sys.getenv("SEQTRIE_TEST_SEED")
+
...[truncated]...
ctor
Loading required package: GenomeInfoDb
Attaching package: 'Biostrings'
The following object is masked from 'package:base':
strsplit
Attaching package: 'pwalign'
The following objects are masked from 'package:Biostrings':
PairwiseAlignments, PairwiseAlignmentsSingleSubject, aligned,
alignedPattern, alignedSubject, compareStrings, deletion,
errorSubstitutionMatrices, indel, insertion, mismatchSummary,
mismatchTable, nedit, nindel, nucleotideSubstitutionMatrix,
pairwiseAlignment, pattern, pid, qualitySubstitutionMatrices,
stringDist, unaligned, writePairwiseAlignments
Test seed: 1780639412
[1] "Checking hamming search correctness"
[1] "Checking levenshtein search correctness"
Error in unlist(substitutionMatrix, substitutionMatrix) :
'recursive' must be a length-1 vector
Calls: <Anonymous> ... mpi.XStringSet.pairwiseAlignment -> XStringSet.pairwiseAlignment -> array -> unlist
Execution halted
Check History
ERROR 12 OK · 0 NOTE · 0 WARNING · 1 ERROR · 0 FAILURE Jun 4, 2026
tests
Running ‘test_RadixForest.R’ [4s/3s]
Running ‘test_RadixTree.R’ [10s/13s]
Running ‘test_StarTree.R’ [72s/94s]
Running ‘test_pairwise.R’ [4s/8s]
Running the tests in ‘tests/test_pairwise.R’ failed.
Complete output:
> # This test file tests the
...[truncated]...
search correctness"
Error in unlist(substitutionMatrix, substitutionMatrix) :
'recursive' must be a length-1 vector
Calls: <Anonymous> ... mpi.XStringSet.pairwiseAlignment -> XStringSet.pairwiseAlignment -> array -> unlist
Execution halted
OK 12 OK · 0 NOTE · 0 WARNING · 0 ERROR · 0 FAILURE Apr 25, 2026
NOTE 11 OK · 3 NOTE · 0 WARNING · 0 ERROR · 0 FAILURE Apr 22, 2026
installed package size
installed size is 6.0Mb
sub-directories of 1Mb or more:
data 1.1Mb
libs 4.4Mb
package dependencies
Package suggested but not available for checking: ‘pwalign’
for GNU extensions in Makefiles
GNU make is a SystemRequirements.
ERROR 10 OK · 3 NOTE · 0 WARNING · 1 ERROR · 0 FAILURE Apr 18, 2026
whether package can be installed
Installation failed. See 'd:/Rcompile/CRANpkg/local/4.6/seqtrie.Rcheck/00install.out' for details.
installed package size
installed size is 6.0Mb
sub-directories of 1Mb or more:
data 1.1Mb
libs 4.4Mb
package dependencies
Package suggested but not available for checking: ‘pwalign’
for GNU extensions in Makefiles
GNU make is a SystemRequirements.
NOTE 11 OK · 3 NOTE · 0 WARNING · 0 ERROR · 0 FAILURE Mar 10, 2026
installed package size
installed size is 6.0Mb
sub-directories of 1Mb or more:
data 1.1Mb
libs 4.4Mb
package dependencies
Package suggested but not available for checking: ‘pwalign’
for GNU extensions in Makefiles
GNU make is a SystemRequirements.