Finding composite regulatory patterns in DNA sequences.
Pattern discovery in unaligned DNA sequences is a fundamental problem in computational biology with important applications in finding regulatory signals. Current approaches to pattern discovery focus on monad patterns that correspond to relatively short contiguous strings. However, many of the actual regulatory signals are composite patterns that are groups of monad patterns that occur near each other. A difficulty in discovering composite patterns is that one or both of the component monad patterns in the group may be 'too weak'. Since the traditional monad-based motif finding algorithms usually output one (or a few) high scoring patterns, they often fail to find composite regulatory signals consisting of weak monad parts. In this paper, we present a MITRA (MIsmatch TRee Algorithm) approach for discovering composite signals. We demonstrate that MITRA performs well for both monad and composite patterns by presenting experiments over biological and synthetic data.
Eskin
Eleazar
E
Department of Computer Science, Columbia University, New York, 10027 NY, USA. eeskin@cs.columbia.edu
Pevzner
Pavel A
PA
D000465:Algorithms; D020029:Base Pairing / Q000235:genetics; D001483:Base Sequence; D002874:Chromosome Mapping / Q000379:methods*; D020869:Gene Expression Profiling / Q000379:methods*; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated; D010802:Phylogeny; D012045:Regulatory Sequences, Nucleic Acid / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid; D012984:Software