Efficient sequential and parallel algorithms for finding edit distance based motifs

BMC Genomics

Research

Peng Xiao¹  Sanguthevar Rajasekaran¹  Soumitra Pal¹ 

[1] Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, 06269, Storrs, CT, USA;

关键词: Motif;    Edit distance;    Trie;    Radix sort;   

DOI  :  10.1186/s12864-016-2789-9

来源: Springer

【 摘 要 】

BackgroundMotif search is an important step in extracting meaningful patterns from biological data. The general problem of motif search is intractable and there is a pressing need to develop efficient, exact and approximation algorithms to solve this problem. In this paper, we present several novel, exact, sequential and parallel algorithms for solving the (l,d) Edit-distance-based Motif Search (EMS) problem: given two integers l,d and n biological strings, find all strings of length l that appear in each input string with atmost d errors of types substitution, insertion and deletion.MethodsOne popular technique to solve the problem is to explore for each input string the set of all possible l-mers that belong to the d-neighborhood of any substring of the input string and output those which are common for all input strings. We introduce a novel and provably efficient neighborhood exploration technique. We show that it is enough to consider the candidates in neighborhood which are at a distance exactly d. We compactly represent these candidate motifs using wildcard characters and efficiently explore them with very few repetitions. Our sequential algorithm uses a trie based data structure to efficiently store and sort the candidate motifs. Our parallel algorithm in a multi-core shared memory setting uses arrays for storing and a novel modification of radix-sort for sorting the candidate motifs.ResultsThe algorithms for EMS are customarily evaluated on several challenging instances such as (8,1), (12,2), (16,3), (20,4), and so on. The best previously known algorithm, EMS1, is sequential and in estimated 3 days solves up to instance (16,3). Our sequential algorithms are more than 20 times faster on (16,3). On other hard instances such as (9,2), (11,3), (13,4), our algorithms are much faster. Our parallel algorithm has more than 600 % scaling performance while using 16 threads.ConclusionsOur algorithms have pushed up the state-of-the-art of EMS solvers and we believe that the techniques introduced in this paper are also applicable to other motif search problems such as Planted Motif Search (PMS) and Simple Motif Search (SMS).

【 授权许可】

CC BY   
© The Author(s) 2016

【 图 表 】

Fig. 9

Fig. 1

12951_2015_155_Article_IEq34.gif

12951_2015_155_Article_IEq33.gif

12951_2015_155_Article_IEq32.gif

Fig. 1

12864_2016_2889_Article_IEq3.gif

Fig. 1

Fig. 2

Fig. 2

Fig. 2

Fig. 1

12951_2017_270_Article_IEq10.gif

Fig. 8

Fig. 3

Fig. 3

Fig. 7

12951_2015_111_Article_IEq5.gif

Fig. 1

12951_2015_155_Article_IEq30.gif

Fig. 5

Fig. 6

12951_2017_270_Article_IEq9.gif

Fig. 2

12951_2017_270_Article_IEq8.gif

Fig. 1

12951_2015_111_Article_IEq4.gif

Fig. 1

13100_2023_302_Article_IEq7.gif

12951_2015_155_Article_IEq25.gif

12951_2015_155_Article_IEq24.gif

Fig. 2

12951_2017_270_Article_IEq5.gif

Fig. 3

Fig. 1

12951_2015_111_Article_IEq1.gif

Fig. 6

Fig. 4

Fig. 1

Fig. 1

12951_2015_155_Article_IEq23.gif