从字符串序列中查找重复的子串

Question

我有许多字符串序列。从每个序列中，我必须找到所有这样的子串，它们至少重复一些最小阈值时间(Th)。

例如，如果字符串序列中的一个是"aboaboaboaboaboabcabcabcabcab“。如果最小重复阈值(th=4)，则特定序列子串是“ab0”、"boa“、"oab”、"abc“、"bca”、"cab“。

我用蛮力解决了这个问题。但是如果我们将该方法应用于至少100000个这样的序列，那么它在R中需要几分钟。我想在几秒钟内找到100000个序列中的所有这样的子串。

我想在R中实现它。

Answer 1

你可以使用combn，但据我所知，它不尊重顺序，所以得到的组合比遵循顺序的组合要多得多，例如，

s <- "aboaboaboaboaboabcabcabcabcab"
combos <- combn(strsplit(s, "")[[1]], 3, paste0, collapse="")
combos[1:5]
[1] "abo" "aba" "abb" "abo" "aba"

Answer 2

这似乎是有效的(假设您需要3个字母的子字符串)。

str <- "aboaboaboaboaboabcabcabcabcab"
th  <- 4

sub <- sapply(1:(nchar(str)-2),function(i)substr(str,i,i+2))
sub[which(table(sub)>=th)]
# [1] "abo" "boa" "oab" "abo" "boa" "oab"

以及一些长度为100,000的字符串的基准测试。

get.repeats <- function(str,n,k){
  sub <- sapply(1:(nchar(str)-n+1),function(i)substr(str,i,i+n-1))
  sub[which(table(sub)>=k)]
}
# benchmark
set.seed(1)
str <- paste(sample(c("A","C","G","T"),1e5,replace=TRUE),collapse="")
library(microbenchmark)
microbenchmark(get.repeats(str,3,4),times=10)
# Unit: seconds
#                    expr      min      lq   median       uq      max neval
#  get.repeats(str, 3, 4) 1.835401 1.86695 1.886206 1.917245 2.035076    10

所以这大约在2秒内运行。