zbMATH — the first resource for mathematics

Discovering cis-regulatory modules by optimizing barbecues. (English) Zbl 1172.92013
Summary: Gene expression in eukaryotic cells is regulated by a complex network of interactions, where transcription factors and their binding sites on the genomic DNA play a determining role. As transcription factors rarely, if ever, act in isolation, binding sites of interacting factors are typically arranged in close proximity forming so-called \(c\)is-regulatory modules. Even when the individual binding sites are known, module discovery remains a hard combinatorial problem, which we formalize here as the Best Barbecue Problem. It asks for simultaneously stabbing a maximum number of differently colored intervals from \(K\) arrangements of colored intervals. This geometric problem turns out to be an elementary, yet previously unstudied combinatorial optimization problem of detecting common edges in a family of hypergraphs, a decision version of which we show here to be NP-complete.
Due to its relevance in biological applications, we propose algorithmic variations that are suitable for the analysis of real data sets comprising either many sequences or many binding sites. Being based on set systems induced by interval arrangements, our problem setting generalizes to discovering patterns of co-localized item sets in non-sequential objects that consist of corresponding arrangements or induce set systems of co-localized items. In fact, our optimization problem is a generalization of the popular concept of frequent item set mining.
92C40 Biochemistry, molecular biology
90C27 Combinatorial optimization
05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
PDF BibTeX Cite
Full Text: DOI
[1] Aerts, S.; Van Loo, P.; Moreau, Y.; De Moor, B., A genetic algorithm for the detection of new cis-regulatory modules in sets of coregulated genes, Bioinformatics, 20, 1974-1976, (2004)
[2] Agrawal, R.; Imieliński, T.; Swami, A., Mining association rules between sets of items in large databases, ACM SIGMOD record, 22, 207-216, (1993)
[3] Arnone, M.I.; Davidson, E.H., The hardwiring of development: organization and function of genomic regulatory systems, Development, 124, 1851-1864, (1997)
[4] Azarenok, A.; Krikun, V., A clique in a \(n\)-partite graph and optimal orientation of functional blocks of integral schemes, Izv. akad. nauk BSSR, ser. fiz.-mat. nauk (proc. ac. sc. belarus. phys.-math. ser.), 2, 8-15, (1988), (in Russian) Zentralblatt MATH accession number Zbl 0652.05057 · Zbl 0652.05057
[5] Beal, M.P.; Bergeron, A.; Corteel, S.; Raffinot, M., An algorithmic view of gene teams, Theoret. comput. sci., 320, 395-418, (2004) · Zbl 1043.92006
[6] Ben-Tabou de Leon, S.; Davidson, E.D., Gene regulation: gene control network in development, Ann. rev. biophys. biomol. struct., 36, 191-212, (2007)
[7] Berman, B.P.; Pfeiffer, B.D.; Laverty, T.R.; Salzberg, S.L.; Rubin, G.M.; Eisen, M.B.; Celniker, S.E., Computational identification of developmental enhancers: conservation and function of transcription factor binding-site clusters in drosophila melanogaster and drosophila pseudoobscura, Genome biol., 5, R61, (2004)
[8] Blanchette, M.; Bataille, A.R.; Chen, X.; Poitras, C.; Laganiere, J.; Lefebvre, C.; Deblois, G.; Giguere, V.; Ferretti, V.; Bergeron, D., Genome-wide computational prediction of transcriptional regulatory modules reveals new insights into human gene expression, Genome res., 16, 656, (2006)
[9] Blanchette, M.; Tompa, M., : A program designed for phylogenetic footprinting, Nucleic acids res., 31, 3840-3842, (2003)
[10] Chuzhanova, N.A.; Krawczak, M.; Nemytikova, L.A.; Gusev, V.D.; Cooper, D.N., Promoter shuffling has occurred during the evolution of the vertebrate growth hormone gene, Gene, 254, 9-18, (2000)
[11] T.E.P. Consortium, The ENCODE project consortium, identification and analysis of functional elements in 1% of the human genome by the ENCODE pilot project, Nature, 447, 799-816, (2007)
[12] Davidson, E., Genomic regulatory systems, (2001), Academic Press San Diego
[13] Doniger, S.W.; Fay, J.C., Frequent gain and loss of functional transcription factor binding sites, Plos comp. biol., 3, e99, (2007)
[14] Erives, A.; Levine, M., Coordinate enhancers share common organizational features in the drosophila genome, Proc. natl. acad. sci. USA, 101, 3851-3856, (2004)
[15] Heinemeyer, T.; Wingender, E.; Reuter, I.; Hermjakob, H.; Kel, A.E.; Kel, O.V.; Ignatieva, E.V.; Ananko, E.A.; Podkolodnaya, O.A.; Kolpakov, F.A.; Podkolodny, N.L.; Kolchanov, N.A., Databases on transcriptional regulation: TRANSFAC, TRRD, and COMPEL, Nucleic acids res., 26, 364-370, (1998)
[16] Hughes, J.D.; Estep, P.W.; Tavazoie, S.; Church, G.M., Computational identification of cis-regulatory elements associated with groups of functionally related genes in saccharomyces cerevisiae, J. mol. biol., 296, 1205-1214, (2000)
[17] O.V. Kel-Margoulis, T.G. Ivanova, E. Wingender, A.E. Kel, Automatic annotation of genomic regulatory sequences by searching for composite clusters, in: Proc. Pac. Symp. Biocomput., 2002, pp. 187-198
[18] Kim, J.; Seo, J.; Lee, Y.S.; Kim, S., : integrated analysis database for predicted transcription regulatory elements, Bioinformatics, 21, 548-550, (2005)
[19] Ludwig, M.Z.; Bergman, C.; Patel, N.H.; Kreitman, M., Evidence for stabilizing selection in a eukaryotic enhancer element, Nature, 403, 564-567, (2000)
[20] McGinnis, W.; Krumlauf, R., Homeobox genes and axial patterning, Cell, 68, 283-302, (1992)
[21] Menzel, P.; Stadler, P.F.; Mosig, A., Tanimoto’s best barbecue: discovering regulatory modules using tanimoto scores, (), 68-77
[22] Moses, A.M.; Pollard, D.A.; Nix, D.A.; Iyer, V.N.; Li, X.Y.; Biggin, M.D.; Eisen, M.B., Large-scale turnover of functional transcription factor binding sites in drosophila, Plos comp. biol., 2, e130, (2006)
[23] Noto, K.; Craven, M., Learning probabilistic models of cis-regulatory modules that represent logical and spatial aspects, Bioinformatics, 23, e156-e162, (2007)
[24] Pennisi, E., Searching for the genome’s second code, Science, 306, 632-635, (2004)
[25] Perco, P.; Kainz, A.; Mayer, G.; Lukas, A.; Oberbauer, R.; Mayer, B., Detection of coregulation in differential gene expression profiles, Biosystems, 82, 235-247, (2005)
[26] A. Philippakis, F. He, M. Bulyk, Modulefinder: A tool for computational discovery of cis regulatory modules, in: Proc. Pac. Symp. Biocomput., 2005, pp. 519-30
[27] Prohaska, S.; Fried, C.; Flamm, C.; Wagner, G.; Stadler, P., Surveying phylogenetic footprints in large gene clusters: applications to hox cluster duplications, Mol. phyl. evol., 31, 581-604, (2004)
[28] Sandelin, A.; Pär Engström, W.A.; Wasserman, W.; Lenhard, B., JASPAR: an open access database for eukaryotic transcription factor binding profiles, Nucleic acids res., 32, D91-D94, (2004)
[29] Sanges, R.; Kalmar, E.; Claudiani, P.; D’Amato, M.; Muller, F.; Stupka, E., Shuffling of cis-regulatory elements is a pervasive feature of the vertebrate lineage, Genome biol., 7, R56, (2006)
[30] Sharan, R.; Ben-Hur, A.; Loots, G.G.; Ovcharenko, I., : cis-regulatory module explorer for the human genome, Nucleic acids res., 32, W253-W256, (2004)
[31] Sharir, M.; Agarwal, P., Arrangements and their applications, (), 49-119 · Zbl 0948.52011
[32] Sinha, S.; van Nimwegen, E.; Siggia, E.D., A probabilistic method to detect regulatory modules, Bioinformatics, 19, i292-i301, (2003)
[33] Smith, A.D.; Sumazin, P.; Zhang, M.Q., Tissue-specific regulatory elements in Mammalian promoters, Mol. systems biol., 3, 73, (2007)
[34] Tanay, A.; Regev, A.; Shamir, R., Conservation and evolvability in regulatory networks: the evolution of ribosomal regulation in yeast, Proc. natl. acad. sci. USA, 102, 7203-7208, (2005)
[35] Wassermann, W.W.; Sandelin, A., Applied bioinformatics for the identification of regulatory elements, Nat. rev. genet., 5, 276-287, (2004)
[36] Wray, G.A.; Hahn, M.W.; Abouheif, E.; Balhoff, J.P.; Pizer, M.; Rockman, M.V.; Romano, L.A., The evolution of transcriptional regulation in eukaryotes, Mol. biol. evol., 20, 1377-1419, (2003)
[37] Yuh, C.H.; Bolouri, H.; Davidson, E.H., Genomic cis-regulatory logic: experimental and computational analysis of a sea urchin gene, Science, 279, 1896-1902, (1998)
[38] Zakany, J.; Duboule, D., The role of hox genes during vertebrate limb development, Curr. opin. genet. dev., 17, 359-366, (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.