如何合并显示最常见字符的相似字符串
El *_*vid 6 string r bioinformatics
在一个数据帧中，我有一个字符串列表，这些字符串彼此相似，但相差％。我想将这些通用字符串组合成一个在每个位置具有最通用字符的字符串。
数据框如下所示：
pattern Freq score rank
DT%E 37568 1138.4242 1
%TGE 37666 1018.0000 2
D%GE 37641 1017.3243 3
DTG% 37665 965.7692 4
%VGNE 34234 684.6800 5
SVGN% 34281 634.8333 6
SV%NE 34248 634.2222 7
SVG%E 34265 623.0000 8
%LGNE 41098 595.6232 9
SL%NE 41086 595.4493 10
SLGN% 41200 564.3836 11
SPT%AYNE 35082 539.7231 12
SP%AAYNE 35094 531.7273 13
SPTA%YNE 35061 531.2273 14
SPTAA%NE 35225 518.0147 15
SPTAAYN% 35144 516.8235 16
%PTAAYNE 35111 516.3382 17
S%TAAYNE 35100 516.1765 18
SPTAAY%E 35130 509.1304 19
SLG%E 41467 450.7283 20
我正在尝试从模式列中添加最可能包含字符串的另一列
pattern Freq score rank true_string
DT%E 37568 1138.4242 1 DTGE
%TGE 37666 1018.0000 2 DTGE
D%GE 37641 1017.3243 3 DTGE
DTG% 37665 965.7692 4 DTGE
%VGNE 34234 684.6800 5 SVGNE
SVGN% 34281 634.8333 6 SVGNE
SV%NE 34248 634.2222 7 SVGNE
SVG%E 34265 623.0000 8 SVGNE
%LGNE 41098 595.6232 9 SLGNE
SL%NE 41086 595.4493 10 SLGNE
SLGN% 41200 564.3836 11 SLGNE
SPT%AYNE 35082 539.7231 12 SPTAAYNE
SP%AAYNE 35094 531.7273 13 SPTAAYNE
SPTA%YNE 35061 531.2273 14 SPTAAYNE
SPTAA%NE 35225 518.0147 15 SPTAAYNE
SPTAAYN% 35144 516.8235 16 SPTAAYNE
%PTAAYNE 35111 516.3382 17 SPTAAYNE
S%TAAYNE 35100 516.1765 18 SPTAAYNE
SPTAAY%E 35130 509.1304 19 SPTAAYNE
SLG%E 41467 450.7283 20 SLGNE
这是一个棘手但有趣的问题。
这是应该给你一些想法的东西（并重现你的预期输出）；但请注意，这在某种程度上是一种实证方法，做出以下假设：
总有一些
>=2模式属于相同的true_string；这对于（分层）聚类方法的工作是必要的（见下文）。如果您有<2定义 a 的模式true_string，则这将不起作用，这是有道理的，因为同一位置的两个字符出现的频率相同。所有
patterns 的长度相同；即我们只考虑单个字符替换，但不考虑插入/删除。
方法
我们利用该库stringdist来计算字符串相似度。stringdistmatrix提供各种距离度量（Levenshtein、Hamming...，请参阅?stringdist::stringdistmatrix详细信息）。在本例中，我们使用method = "qgram"它是因为它会产生与您的预期输出一致的分组（因此是早期的“经验”警告）。我不知道这对您的真实数据的概括效果如何，因此请务必记住，您可能需要尝试不同的方法methods 才能找到“符合”您的期望的距离相似度度量。
计算出字符串距离矩阵后，我们使用层次聚类对字符串进行聚类；我们grp根据 的垂直距离切割树来添加标签v = 2，然后使用自定义get_consensus_string函数来推断每个 的共识字符串grp；如一开始所述，该函数假设一个字符串中的所有字符串都grp具有相同的长度，并且对于字符串中的每个位置，选择出现频率最大的字符。
代码
首先是自定义get_consensus_string函数
library(tidyverse)
get_consensus_string <- function(x) {
map_dfc(x, str_split, "") %>%
rowid_to_column("pos") %>%
gather(k, v, -pos) %>%
group_by(pos, v) %>%
add_count() %>%
group_by(pos) %>%
filter(n == max(n)) %>%
arrange(pos, desc(v)) %>%
dplyr::slice(1) %>%
pull(v) %>%
paste0(collapse = "")
}
grp我们现在可以根据来自 的字符串相似性距离矩阵的层次聚类结果添加标签stringdist::stringdistmatrix；我凭经验以垂直距离v = 2（这是一个可能需要调整的参数）切割树；一旦我们有了标签，grp我们就添加共识字符串。
library(stringdist)
df %>%
mutate(grp = cutree(hclust(stringdistmatrix(df$pattern, method = "qgram")), h = 2)) %>%
group_by(grp) %>%
mutate(true_string = get_consensus_string(pattern)) %>%
ungroup()
## A tibble: 20 x 6
# pattern Freq score rank grp true_string
# <fct> <int> <dbl> <int> <int> <chr>
# 1 DT%E 37568 1138. 1 1 DTGE
# 2 %TGE 37666 1018 2 1 DTGE
# 3 D%GE 37641 1017. 3 1 DTGE
# 4 DTG% 37665 966. 4 1 DTGE
# 5 %VGNE 34234 685. 5 2 SVGNE
# 6 SVGN% 34281 635. 6 2 SVGNE
# 7 SV%NE 34248 634. 7 2 SVGNE
# 8 SVG%E 34265 623 8 2 SVGNE
# 9 %LGNE 41098 596. 9 3 SLGNE
#10 SL%NE 41086 595. 10 3 SLGNE
#11 SLGN% 41200 564. 11 3 SLGNE
#12 SPT%AYNE 35082 540. 12 4 SPTAAYNE
#13 SP%AAYNE 35094 532. 13 4 SPTAAYNE
#14 SPTA%YNE 35061 531. 14 4 SPTAAYNE
#15 SPTAA%NE 35225 518. 15 4 SPTAAYNE
#16 SPTAAYN% 35144 517. 16 4 SPTAAYNE
#17 %PTAAYNE 35111 516. 17 4 SPTAAYNE
#18 S%TAAYNE 35100 516. 18 4 SPTAAYNE
#19 SPTAAY%E 35130 509. 19 4 SPTAAYNE
#20 SLG%E 41467 451. 20 3 SLGNE
您可以看到最终的代码非常干净，并且重现了您的预期输出。
一些进一步的注释/评论
有两个问题可能值得讨论：（1）如何选择合适的距离度量；（2）在哪里砍伐树木。
关于第一个问题，经验方法是尝试不同的度量并在patterns 进行分层聚类后可视化树状图。
例如，method = "qgram"你会做
mat <- as.matrix(stringdistmatrix(df$pattern, method = "qgram"))
rownames(mat) <- df$pattern
colnames(mat) <- df$pattern
plot(hclust(as.dist(mat)))
一旦您对聚类结果感到满意，我们就可以继续。
关于砍伐树木，一种实际/务实的方法是检查树状图并找到砍伐树木的合适高度（在我们的例子中为v = 2）；或者，如果您知道 unique 的数量，则可以在withtrue_string中指定组的数量。cutreek
用更专业的术语来说，树状图的高度与使用完全链接的组之间的距离相关联（即基于最不相似的对测量距离）。由于组之间的距离又基于patterns 之间的 q-gram-距离，因此可以将高度与两个patterns 之间的 q-gram-距离相关联，即两个 s 的 N-gram 向量之间的绝对差pattern。