<p>由于需求被澄清了几次,我将发布一个基于图论的新解决方案(实际上,这个想法属于@Martin Wettstein,请参见对问题的评论)。当然,在循环图的情况下可能会有问题,但这将是另一个问题</p>
<p>脚本从邻接矩阵创建图形,并计算通过图形的最长路径(直径)</p>
<p>由于提供的真实数据子集不包含连续序列,我将使用以前版本答案中的虚拟数据</p>
<pre><code>library(dplyr)
library(igraph)
dat_txt <- "MacroNode Prefix Suffix
GC T A
CA C C
AC C T
CT A A
GC T A
CA G C
AC C T
CT A A"
# Concat strings
dat <- read.table(text = dat_txt, header = TRUE)
res <- dat %>%
mutate(cur = paste0(MacroNode, Suffix),
follow = paste0(Prefix, MacroNode),
full = paste0(Prefix, MacroNode, Suffix))
# Prepare adjacency matrix
edge_mat <- outer(seq_len(nrow(res)), seq_len(nrow(res)), function(r, c) {
return(res[r, "cur"] == res[c, "follow"])
})
# Construct graph
res_g <- graph_from_adjacency_matrix(edge_mat)
# Get the path with maximum length
g_diam <- get_diameter(res_g)
# Concatenate longest path
long_seq <- paste(res[g_diam, "full"], collapse = "")
</code></pre>
<p>结果如下:</p>
<pre><code>> long_seq
[1] "TGCAGCACCACTACTA"
</code></pre>