Finding composite regulatory patterns in DNA sequences

• Published in: Bioinformatics 2002-07, Vol.18 (suppl-1), p.S354-S363
• Main Authors: Eskin, Eleazar, Pevzner, Pavel A.
• Format: Article
• Language: English
• Subjects: Algorithms; Base Pairing - genetics; Base Sequence; Chromosome Mapping - methods; Gene Expression Profiling - methods; Mitra; Molecular Sequence Data; Pattern Recognition, Automated; Phylogeny; Regulatory Sequences, Nucleic Acid - genetics; Sequence Alignment - methods; Sequence Analysis, DNA - methods; Sequence Homology, Nucleic Acid; Software
• ISSN: 1367-4803; 1460-2059; 1367-4811
• DOI: 10.1093/bioinformatics/18.suppl_1.S354

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. Availability: MITRA is available at http://www.cs.columbia.edu/compbio/mitra/ Contact: [e-mail] Keywords: regulatory motif finding; pattern finding; dyad motifs.