Efficient composite pattern finding from monad patterns. (27th December 2006)

• Record Type: Journal Article
• Authors: Zhou, Jianjun; Sander, Jorg; Lin, Guohui
• Is Part Of: International journal of bioinformatics research and applications. Volume 3:Number 1(2007)
• Page Start: 86
• Page End: 99
• Publication Date: 2006-12-27
• Subjects: pattern finding -- monad patterns -- composite patterns -- runtime complexity -- bioinformatics -- pattern recognition -- DNA sequences; Bioinformatics -- Periodicals; 570.285
• Languages: English
• ISSNs: 1744-5485

Abstract

Automatically identifying frequent composite patterns in DNA sequences is an important task in bioinformatics, especially when all the basic elements (or monad patterns) of a composite pattern are weak. In this paper, we compare one straightforward approach to assemble the monad patterns into composite patterns to two other rather complex approaches. Both our theoretical analysis and empirical results show that this overlooked straightforward method can be several orders of magnitude faster. Furthermore, different from the previous understandings, the empirical results show that the runtime superiority among the three approaches is closely related to the insignificance of the monad patterns.