我有 n 个序列，每个序列长度为 30 亿（人类基因组）。我正在寻找有效的方法来存储/表示这些 n 个字符串。我能想到的一种自然方式是图，其中节点可以存储这些序列之间的公共子字符串，并且在我们看到变化的节点和一组路径之间存在有向边 P = P1 。. . Pq 其中每条路径代表原始序列..
例如：
假设我们有四个字符串 S1 = ATCGGCT, S2 = ATCGATT, S3 = GTCGGCT, S4 = GTCGATT。那么Graph应该如下
我面临的问题是如何找到在 n 序列中常见的最大公共子序列，如果不是，则为 n-1 序列，依此类推。任何人都可以指向我可以获得方向或伪代码的资源吗？提前致谢。