Minimal Absent Words in a Sliding Window and Applications to On-Line Pattern Matching
Minimal Absent Words in a Sliding Window and Applications to On-Line Pattern Matching
复制标题
滑动窗口中的最小缺失词及其在在线模式匹配中的应用
DOI：
10.1007/978-3-662-55751-8_14
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Yann Ramusat
中科院分区：
文献类型：
--
作者：
M. Crochemore;Alice Héliou;G. Kucherov;L. Mouchard;S. Pissis;Yann Ramusat
如果在y中出现所有适当的因素，则缺乏（或禁止）单词y。 y的单词（Crochemore等人在INF过程中Lett 67：111–117，1998; Belazzougui等人在ESA 8125：133–144，2013; Barton等人BMC Bioinform 15：388，2014）。最小缺乏单词用于数据压缩（Crochemore等人在Proc IEEE 88：1756–1768，2000，Theoret Comput Sci 526：108-119，2014中的OTA和Morita），以及使用公制的无对齐序列比较基于最小的单词（理论计算机科学学士学位450：109–116，2012年）也用于分子生物学。发现人类基因组的单词在埃博拉病毒基因组中的编码区域起起作用（Silva等人在生物信息学中，2015年3月31日：2421–2425，2015）。 - 匹配。特别是，我们提出了一个算法，给定一个模式x和一个文本y，计算x和每个大小| x |的距离。 \ sigma | y |）\），其中\（\ sigma \）是字母的大小。 MATHCAL {O}（\ Sigma | X |）\） - 空间算法，以计算y上每个大小| x |的最小单词，以及对最小缺失单词的一些新组合洞察。
An absent (or forbidden) word of a word y is a word that does not occur in y. It is then called minimal if all its proper factors occur in y. There exist linear-time and linear-space algorithms for computing all minimal absent words of y (Crochemore et al. in Inf Process Lett 67:111–117, 1998; Belazzougui et al. in ESA 8125:133–144, 2013; Barton et al. in BMC Bioinform 15:388, 2014). Minimal absent words are used for data compression (Crochemore et al. in Proc IEEE 88:1756–1768, 2000, Ota and Morita in Theoret Comput Sci 526:108–119, 2014) and for alignment-free sequence comparison by utilizing a metric based on minimal absent words (Chairungsee and Crochemore in Theoret Comput Sci 450:109–116, 2012). They are also used in molecular biology; for instance, three minimal absent words of the human genome were found to play a functional role in a coding region in Ebola virus genomes (Silva et al. in Bioinformatics 31:2421–2425, 2015). In this article we introduce a new application of minimal absent words for on-line pattern matching. Specifically, we present an algorithm that, given a pattern x and a text y, computes the distance between x and every window of size |x| on y. The running time is \(\mathcal {O}(\sigma |y|)\), where \(\sigma \) is the size of the alphabet. Along the way, we show an \(\mathcal {O}(\sigma |y|)\)-time and \(\mathcal {O}(\sigma |x|)\)-space algorithm to compute the minimal absent words of every window of size |x| on y, together with some new combinatorial insight on minimal absent words.