Alignment-free sequence comparison using absent words
Alignment-free sequence comparison using absent words
复制标题
DOI：
10.1016/j.ic.2018.06.002
复制
发表时间：
2018-10-01
影响因子：
1
通讯作者：
Pissis, Solon R.
中科院分区：
文献类型：
--
作者：
Charalampopoulos, Panagiotis;Crochemore, Maxime;Pissis, Solon R.
序列比较是几乎所有比较基因组分析的先决条件。它通常通过序列对准技术实现，这些技术在计算上昂贵。这导致对无对齐技术的研究增加，这些技术基于指代序列组成的构成模式的措施。这些度量（例如Q-gram距离）通常相对于序列的长度来计算。在本文中，我们关注以下互补思想：如何根据序列中未发生的信息有效地比较两个序列。如果一个序列不在序列中发生，则单词是某个序列的单词。如果其所有适当因素出现在序列中，则缺乏单词是最小的。在这里，我们介绍了第一个线性时间和线性空间算法，以通过考虑所有最小的缺乏单词来比较两个序列。在此过程中，我们提出了组合兴趣的结果，并扩展了提出的技术以比较圆序。我们还提出了一种算法，鉴于长度为n的单词x，它计算了最大的整数，该整数的所有X的所有因素都以某些最小的x在时代和空间o（n）中的x词最小而出现。最后，我们表明，在单词的最小单词的最小单词数量上，已知的渐近上限很紧。 （c）2018 Elsevier Inc.保留所有权利。
Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realised by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as q-gram distance, are usually computed in time linear with respect to the length of the sequences. In this paper, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an absent word of some sequence if it does not occur in the sequence. An absent word is minimal if all its proper factors occur in the sequence. Here we present the first linear-time and linear-space algorithm to compare two sequences by considering all their minimal absent words. In the process, we present results of combinatorial interest, and also extend the proposed techniques to compare circular sequences. We also present an algorithm that, given a word x of length n, computes the largest integer for which all factors of x of that length occur in some minimal absent word of x in time and space O(n). Finally, we show that the known asymptotic upper bound on the number of minimal absent words of a word is tight. (C) 2018 Elsevier Inc. All rights reserved.