Abstract
The problem of finding conserved motifs given a set of DNA sequences is among the most fundamental problems in computational biology, with important applications in locating regulatory sites from co-expressed genes. Traditionally, two classes of approaches are used to address the problem: sample-driven approaches focus on finding the locations of the motif instances directly, while pattern-driven approaches focus on finding a consensus string or a profile directly to model the motif. We propose an integrated approach by formulating the motif finding problem as the problem of finding large cliques in k-partite graphs, with the additional requirement that there exists a string s (which may not appear in the given sample) that is close to every motif instance included in such a clique. In this formulation, each clique represents the locations of the motif instances, while the existence of string s ensures that these instances are derived from a common motif pattern. The combined approach provides a better formulation to model motifs than using cliques alone, and the use of k-partite graphs allows the development of a fast and exact divide-and-conquer approach to handle the cases when almost every sequence contains a motif instance. Computational experiments show that this approach is feasible even on the most difficult motif finding problems of moderate size. When many sequences do not contain a motif instance, we complement the above approach by an optimized branch-and-bound algorithm that is much faster than standard clique finding approaches. We will discuss how to further generalize the formulation to better model biological reality.
This work was supported by NSF grant CCR-0311590.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bailey, T.L., Elkan, C.P.: Fitting a mixture model by expectation maximization to discover motifs in biopolymers. In: Proc. of the 2nd Int. Conf. on Intelligent Systems for Mol. Biol (ISMB 1994), pp. 28–36 (1994)
Bomze, I., Budinich, M., Pardalos, P., Pelillo, M.: The maximum clique problem. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, vol. 4, Kluwer Academic, Dordrecht (1999)
Buhler, J., Tompa, M.: Finding motifs using random projections. J. Comp. Biol. 9, 225–242 (2002)
Chen, J., Huang, X., Kanj, I., Xia, G.: Linear FPT reductions and computational lower bounds. In: Proc. of the 34th ACM Symp. on Theory of Computing (STOC 2004), pp. 212–221 (2004)
Eskin, E.: From profiles to patterns and back again: a branch and bound algorithm for finding near optimal motif profiles. In: Proc. of the 8th Ann. Int. Conf. on Comp. Mol. Biol (RECOMB 2004), pp. 115–124 (2004)
Eskin, E., Pevzner, P.A.: Finding composite regulatory patterns in DNA sequences. Bioinformatics 18, S354–S363 (2002)
Gramm, J., Niedermeier, R., Rossmanith, P.: Exact solutions for closest string and related problems. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol. 2223, pp. 441–453. Springer, Heidelberg (2001)
Keich, U., Pevzner, P.A.: Finding motifs in the twilight zone. In: Proc. of the 6th Ann. Int. Conf. on Comp. Mol. Biol (RECOMB 2002), pp. 195–204 (2002)
Lanctot, J.K., Li, M., Ma, B., Wang, S., Zhang, L.: Distinguishing string selection problems. Information and Computation 185, 41–55 (2003)
Lawrence, C.E., Altschul, S.F., Boguski, M.S., Liu, J.S., Neuwald, A.F., Wootton, J.C.: Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment. Science 262, 208–214 (1993)
Liang, S.: cWINNOWER algorithm for finding fuzzy DNA motifs. In: Proc. of the 2nd IEEE Computer Society Bioinformatics Conf. (CSB 2003), pp. 260–265 (2003)
Lukashin, A.V., Engelbrecht, J., Brunak, S.: Multiple alignment using simulated annealing: branch point definition in human mRNA splicing. Nucleic Acids Res 20, 2511–2516 (1992)
Marsan, L., Sagot, M.-F.: Algorithms for extracting structured motifs using a suffix tree with an application to promoter and regulatory site consensus identification. J. Comp. Biol. 7, 345–362 (2000)
Pevzner, P.A., Sze, S.-H.: Combinatorial approaches to finding subtle signals in DNA sequences. In: Proc. of the 8th Int. Conf. on Intelligent Systems for Mol. Biol. (ISMB 2000), pp. 269–278 (2000)
Price, A., Ramabhadran, S., Pevzner, P.A.: Finding subtle motifs by branching from sample strings. Bioinformatics, SII149–155 (2003)
Stormo, G.D., Hartzell, G.W.: Identifying protein-binding sites from unaligned DNA fragments. Proc. Natl. Acad. Sci. USA 86, 1183–1187 (1989)
Sze, S.-H., Gelfand, M.S., Pevzner, P.A.: Finding weak motifs in DNA sequences. In: Pac. Symp. Biocomput (PSB 2002), pp. 235–246 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sze, SH., Lu, S., Chen, J. (2004). Integrating Sample-Driven and Pattern-Driven Approaches in Motif Finding. In: Jonassen, I., Kim, J. (eds) Algorithms in Bioinformatics. WABI 2004. Lecture Notes in Computer Science(), vol 3240. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30219-3_37
Download citation
DOI: https://doi.org/10.1007/978-3-540-30219-3_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23018-2
Online ISBN: 978-3-540-30219-3
eBook Packages: Springer Book Archive