Gagie Travis
Faculty of Computer Science, Dalhousie University, Halifax, Canada.
Dev Lang Theory. 2024 Aug;14791:131-140. doi: 10.1007/978-3-031-66159-4_10. Epub 2024 Jul 27.
Finding maximal exact matches (MEMs) between strings is an important task in bioinformatics, but it is becoming increasingly challenging as geneticists switch to pangenomic references. Fortunately, we are usually interested only in the relatively few MEMs that are longer than we would expect by chance. In this paper we show that under reasonable assumptions we can find all MEMs of length at least between a pattern of length and a text of length in time plus extra time only for each MEM of length at least nearly using a compact index for the text, suitable for pangenomics.
在字符串之间寻找最大精确匹配（MEMs）是生物信息学中的一项重要任务，但随着遗传学家转向泛基因组参考，这一任务变得越来越具有挑战性。幸运的是，我们通常只对相对较少的、比随机预期更长的MEMs感兴趣。在本文中，我们表明，在合理的假设下，我们可以使用适合泛基因组学的文本紧凑索引，在时间内找到长度至少为的模式与长度为的文本之间的所有长度至少为的MEMs，并且对于每个长度至少接近的MEMs，只需要额外的时间。
