Novel algorithms for finding the closest l-mers in biological data
Novel algorithms for finding the closest l-mers in biological data
复制标题
用于查找生物数据中最接近的 l-mers 的新算法
DOI：
10.1109/bibm.2017.8217702
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
S. Rajasekaran
中科院分区：
文献类型：
--
作者：
Xingyu Cai;A. Mamun;S. Rajasekaran
随着下一代测序技术的进步，生物学中已经产生了大量的数据。处理这些数据集的瓶颈在于开发有效的算法来从中提取有用的信息。在生物数据中寻找模式的算法为从大量数据集中提取关键信息铺平了道路。在本文中，我们关注一个基本模式，即最接近的l-mers。给定一组m个生物字符串S1， S2，…，Sm和一个整数l，我们感兴趣的问题是从每个字符串中找到一个l-mer，使得它们之间的距离最小。也就是说，我们要找到m个l-mer X1， X2，…，Xm，使得Xi是Si中的l-mer（对于1≤i≤m），并且这m个l-mer之间的汉明距离是最小的（在所有可能的l-mer中）。这个问题有很多应用。一个非常重要的应用是基序搜索。寻找最接近的l-mer的算法已用于解决(l, d)-motif搜索问题（例如，[1],[2]）。本文针对m = 3的特殊情况，提出了新的精确近似算法。如果序列包含实数，则考虑欧几里得距离度量。
With the advances in the next generation sequencing technology, huge amounts of data have been and get generated in biology. A bottleneck in dealing with such datasets lies in developing effective algorithms for extracting useful information from them. Algorithms for finding patterns in biological data pave the way for extracting crucial information from voluminous datasets. In this paper we focus on a fundamental pattern, namely, the closest l-mers. Given a set of m biological strings S1, S2, …, Sm and an integer l, the problem of interest is that of finding an l-mer from each string such that the distance among them is the least. I.e., we want to find m l-mers X1, X2, …, Xm such that Xi is an l-mer in Si (for 1 ≤ i ≤ m) and the Hamming distance among these m l-mers is the least (from among all such possible l-mers). This problem has many applications. An application of great importance is motif search. Algorithms for finding the closest l-mers have been used in solving the (l, d)-motif search problem (see e.g., [1], [2]). In this paper novel exact and approximate algorithms are proposed for this problem for the special case of m = 3. We consider the Euclidean distance metric if the sequences contain real numbers.