TrieAMD: a scalable and efficient apriori motif discovery approach

Area of Science:

• Bioinformatics
• Computational Biology
• Data Mining

Background:

• Motif discovery, identifying recurring patterns in biological sequences, is a fundamental challenge in bioinformatics.
• The Apriori algorithm is a standard data-mining technique for finding frequent patterns in large datasets.

Purpose of the Study:

• To adapt the classic Apriori algorithm for effective biological motif discovery.
• To introduce and evaluate a novel algorithm, Trie-based Apriori Motif Discovery (TrieAMD), for this purpose.

Main Methods:

• Application of the Apriori algorithm combined with the Trie data structure.
• Implementation of specific modifications to tailor Apriori for motif discovery.
• Performance evaluation using Tompa's benchmark dataset.

Main Results:

• TrieAMD demonstrated superior performance in average sensitivity compared to other tested tools on real datasets.
• The algorithm achieved comparable specificity to existing methods.
• Experimental results confirmed linear time and space scalability.

Conclusions:

• TrieAMD is an effective and efficient algorithm for biological motif discovery.
• The proposed modifications enhance the Apriori algorithm's capability for pattern identification in biological sequences.
• The algorithm's scalability makes it suitable for large-scale bioinformatics applications.