Efficient composite pattern finding from monad patterns.
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.
Zhou
Jianjun
J
Bioinformatics Research Group, Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2E8, Canada. jianjun@cs.ualberta.ca
Sander
Jorg
J
Lin
Guohui
G
D000465:Algorithms; D001331:Automation; D001483:Base Sequence; D019295:Computational Biology / Q000295:instrumentation / Q000379:methods*; D015233:Models, Statistical; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated / Q000379:methods*; D016415:Sequence Alignment; D020539:Sequence Analysis, Protein; D012984:Software; D013997:Time Factors