TrieAMD: a scalable and efficient apriori motif discovery approach. (2015)

• Record Type: Journal Article
• Authors: Al-Turaiki, Isra; Badr, Ghada; Mathkour, Hassan
• Is Part Of: International journal of data mining and bioinformatics. Volume 13:Number 1(2015)
• Page Start: 13
• Page End: 30
• Publication Date: 2015
• Subjects: bioinformatics -- apriori motif discovery -- data mining -- scalability -- Trie -- transcription factor binding sites -- recurring patterns -- biological sequences -- suffix tree -- data structures; Data mining -- Periodicals; Bioinformatics -- Periodicals; 006.312
• Languages: English
• ISSNs: 1748-5673

Abstract

Motif discovery is the problem of finding recurring patterns in biological sequences. It is one of the hardest and long-standing problems in bioinformatics. Apriori is a well-known data-mining algorithm for the discovery of frequent patterns in large datasets. In this paper, we apply the Apriori algorithm and use the Trie data structure to discover motifs. We propose several modifications so that we can adapt the classic Apriori to our problem. Experiments are conducted on Tompa's benchmark to investigate the performance of our proposed algorithm, the Trie-based Apriori Motif Discovery (TrieAMD). Results show that our algorithm outperforms all of the tested tools on real datasets for the average sensitivity measure, which means that our approach is able to discover more motifs. In terms of specificity, the performance of our algorithm is comparable to the other tools. The results also confirm both linear time and linear space scalability of the algorithm.