Skip to content

seqtrie

Radix Tree and Trie-Based String Distances

v0.4.0 · Jun 3, 2026 · GPL-3

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

1 ERROR
12 OK
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)
ERROR r-oldrel-macos-x86_64

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
ERROR r-oldrel-macos-x86_64

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
NOTE r-oldrel-macos-arm64

installed package size

installed size is  6.0Mb
  sub-directories of 1Mb or more:
    data   1.1Mb
    libs   4.4Mb
NOTE r-oldrel-macos-x86_64

package dependencies

Package suggested but not available for checking: ‘pwalign’
NOTE r-oldrel-windows-x86_64

for GNU extensions in Makefiles

GNU make is a SystemRequirements.
ERROR 10 OK · 3 NOTE · 0 WARNING · 1 ERROR · 0 FAILURE Apr 18, 2026
ERROR r-devel-windows-x86_64

whether package can be installed

Installation failed.
See 'd:/Rcompile/CRANpkg/local/4.6/seqtrie.Rcheck/00install.out' for details.
NOTE r-oldrel-macos-arm64

installed package size

installed size is  6.0Mb
  sub-directories of 1Mb or more:
    data   1.1Mb
    libs   4.4Mb
NOTE r-oldrel-macos-x86_64

package dependencies

Package suggested but not available for checking: ‘pwalign’
NOTE r-oldrel-windows-x86_64

for GNU extensions in Makefiles

GNU make is a SystemRequirements.
NOTE 11 OK · 3 NOTE · 0 WARNING · 0 ERROR · 0 FAILURE Mar 10, 2026
NOTE r-oldrel-macos-arm64

installed package size

installed size is  6.0Mb
  sub-directories of 1Mb or more:
    data   1.1Mb
    libs   4.4Mb
NOTE r-oldrel-macos-x86_64

package dependencies

Package suggested but not available for checking: ‘pwalign’
NOTE r-oldrel-windows-x86_64

for GNU extensions in Makefiles

GNU make is a SystemRequirements.

Dependency Network

Dependencies Reverse dependencies Rcpp RcppParallel R6 S7 seqtrie

Version History

updated 0.4.0 ← 0.3.5 diff Jun 3, 2026
new 0.3.5 Mar 10, 2026
updated 0.3.5 ← 0.2.9 diff Oct 19, 2025
updated 0.2.9 ← 0.2.8 diff Mar 1, 2025
updated 0.2.8 ← 0.2.6 diff May 4, 2024
updated 0.2.6 ← 0.2.5 diff Jan 26, 2024
new 0.2.5 Aug 31, 2023