在矩阵中查找子序列

Question

我在网上练习时遇到了这个挑战，“给定一个六字符的字符串数组（DNA字符串）查找是否有突变，如果找到4个等于的子序列就知道是否存在突变连续的字符，可以竖着、横着、斜着找。

所以如果我有下一个字符串数组：

dna = { "ATGCGA", "CAGTGC", "TTATGT", "AGAAGG", "CCCCTA", "TCACTG" }

可能会变成这样的矩阵：

ATGCGA
CAGTGC
TTATGT
AGAAGG
CCCCTA
TCACTG

需要注意的是，字符串的长度不能为6，但所有数组的长度必须相同，以形成NxN矩阵。

算法的输出应该是true，因为它有三个突变。

AXXXXX
XAXXXX
XXAXXX
XXXAXX
XXXXXX
XXXXXX

XXXXXX
XXXXXX
XXXXXX
XXXXXX
CCCCXX
XXXXXX

XXXXGX
XXXXGX
XXXXGX
XXXXGX
XXXXXX
XXXXXX

这些突变中的任何一个都必须使算法 return 它有一个突变。

我试图通过将矩阵链接成 3 个不同的字符串来应用最长的公共子序列，换句话说，一个大列、一个大行和一个大对角线，但这使算法的效率最差。

有人可以指导我吗？

Answer 1

如果我们只是寻找相同字母的连续序列，我们可以在 O(min(m, n)) space 和 O(mn) 时间内解决这个问题，其中 m 是数字行数和 n 列数。从左上角逐行迭代（例如）。对于每个单元格，记录上方、左侧和西北部的连续单元格的数量，如果邻居具有相同的字母，则在每个相应方向的邻居的记录中加 1；否则，记录 1.

（如果我们正在寻找不一定连续的子序列，我们仍然可以用相同的复杂度来解决它，前提是字母表是固定的，但是我们必须为每个记录中的每个字母保留一个状态.)

在矩阵中查找子序列

Find subsequence in matrix

algorithm

matrix

sequence

dna-sequence