实线性和并行多重最长公共子序列(MLCS)算法

各种应用中的信息通常表示为有限字母上的字符序列(例如,DNA或蛋白质序列)。 在大数据时代,这些序列的长度和大小呈爆炸性增长,这给经典的NP-hard问题带来了巨大挑战,即从多个序列中搜索多个最长公共子序列(MLCS)。 在本文中,我们首先揭露了最新的MLCS算法无法应用于长距离和大规模序列比对的事实。 为了克服它们的缺陷并解决更长,更大规模甚至更大的序列比对问题,基于提出的新颖的问题解决模型和各种策略,例如并行拓扑排序,最优计算,中间结果重用,分段计算和序列化等。 ,我们提出了一种新颖的并行MLCS算法。 对合成和现实世界生物序列的数据集进行的详尽实验表明,所提出算法的时间和空间在比对序列中的优势基因数量上仅是线性的,并且所提出的算法明显优于最新的MLCS。算法,适用于更长和更大规模的序列比对。