Efficient sequential and parallel algorithms for finding edit distance based motifs

详细信息    查看全文

• 作者：Soumitra Pal ; Peng Xiao ; Sanguthevar Rajasekaran
• 关键词：Motif ; Edit distance ; Trie ; Radix sort
• 刊名：BMC Genomics
• 出版年：2016
• 出版时间：August 2016
• 年：2016
• 卷：17
• 期：4-supp
• 全文大小：1116KB
• 刊物主题：Life Sciences, general; Microarrays; Proteomics; Animal Genetics and Genomics; Microbial Genetics and Genomics; Plant Genetics & Genomics;
• 出版者：BioMed Central
• ISSN：1471-2164
• 卷排序：17

文摘

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.