Efficient Algorithms for Finding the Closest l-mers in Biological Data
Efficient Algorithms for Finding the Closest l-mers in Biological Data
复制标题
寻找生物数据中最接近的 l-mers 的有效算法
DOI：
10.1109/tcbb.2018.2843364
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Rajasekaran, Sanguthevar
中科院分区：
文献类型：
--
作者：
Cai, Xingyu;Mamun, Abdullah-Al;Rajasekaran, Sanguthevar
随着下一代测序技术的进步，生物学领域已经产生了大量数据。处理此类数据集的瓶颈在于开发有效的算法以从中提取有用信息。用于查找生物数据模式的算法为从大量数据集中提取关键信息铺平了道路。在本文中，我们关注一个基本模式，即最接近的群体。给定一组生物字符串和一个整数，感兴趣的问题是从每个字符串中找到一个聚合体，使得它们之间的距离最小。例如，我们想要找到（for）中的一个mer，并且这些mer之间的汉明距离是最小的（在所有这些可能的mer中）。这个问题有很多应用。一个非常重要的应用是主题搜索。寻找最接近的聚体的算法已被用于解决主题搜索问题（参见例如，，，）。本文针对该问题提出了新颖的精确算法和近似算法。特别是，对 5 进行了全面的实验评估，并进行了进一步的实证研究。如果序列包含实数，我们还将我们的解决方案扩展到欧几里德距离测量度量。
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 the voluminous datasets. In this paper, we focus on a fundamental pattern, namely, the closest-mers. Given a set ofbiological stringsand an integer, the problem of interest is that of finding an-mer from each string such that the distance among them is the least. For example we want to find-merssuch thatis an-mer in(for) and the Hamming distance among these-mers is the least (from among all such possible-mers). This problem has many applications. An application of great importance is motif search. Algorithms for finding the closest-mers have been used in solving the-motif search problem (see e.g., , ). In this paper novel exact and approximate algorithms are proposed for this problem for the case of. In particular, a comprehensive experimental evaluation is performed for, along with a further empirical study ofand 5. We also extend our solution to euclidean distance measurement metric if the sequences contain real numbers.