Discovering cis-regulatory modules by optimizing barbecues

Basit Öğe Kaydı
dc.authorid0000-0001-7266-8323
dc.authorid0000-0002-5016-5191
dc.contributor.authorMosig, Axelen_US
dc.contributor.authorBıyıkoğlu, Türkeren_US
dc.contributor.authorProhaska, Sonja J.en_US
dc.contributor.authorStadler, Peter F.en_US
dc.date.accessioned2015-01-15T23:01:19Z
dc.date.available2015-01-15T23:01:19Z
dc.date.issued2009-05-28
dc.departmentIşık Üniversitesi, Fen Edebiyat Fakültesi, Matematik Bölümüen_US
dc.departmentIşık University, Faculty of Arts and Sciences, Department of Mathematicsen_US
dc.descriptionThis work was supported in part by the DFG Bioinformatics Initiative BIZ-6/1-2.en_US
dc.description.abstractGene expression in eukaryotic cells is regulated by a complex network of interactions, in which 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 cis-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 itemsets 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 itemset mining.en_US
dc.description.sponsorshipWe thank Andreas Dress for helpful comments and Manja Marz for computational assistance. This work was supported in part by the DFG Bioinformatics Initiative BIZ-6/1-2en_US
dc.description.sponsorshipDeutsche Forschungsgemeinschaften_US
dc.description.versionPublisher's Versionen_US
dc.identifier.citationMosig, A., Bıyıkoğlu, T., Prohaska, S. J., & Stadler, P. F. (2009). Discovering cis-regulatory modules by optimizing barbecues. Discrete Applied Mathematics, 157(10), 2458-2468. doi:10.1016/j.dam.2008.06.042en_US
dc.identifier.doi10.1016/j.dam.2008.06.042
dc.identifier.endpage2468
dc.identifier.issn0166-218X
dc.identifier.issn1872-6771
dc.identifier.issue10
dc.identifier.issueSI
dc.identifier.scopus2-s2.0-67349145270
dc.identifier.scopusqualityQ2
dc.identifier.startpage2458
dc.identifier.urihttps://hdl.handle.net/11729/330
dc.identifier.urihttp://dx.doi.org/10.1016/j.dam.2008.06.042
dc.identifier.volume157
dc.identifier.wosWOS:000266758500023
dc.identifier.wosqualityQ3
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.indekslendigikaynakScience Citation Index Expanded (SCI-EXPANDED)en_US
dc.indekslendigikaynakConference Proceedings Citation Index – Science (CPCI-S)en_US
dc.institutionauthorBıyıkoğlu, Türkeren_US
dc.language.isoenen_US
dc.peerreviewedYesen_US
dc.publicationstatusPublisheden_US
dc.publisherElsevier Science Bven_US
dc.relation.ispartofDiscrete Applied Mathematicsen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectGene regulationen_US
dc.subjectCis-regulatory modules (CRMs)en_US
dc.subjectBest barbecue problemen_US
dc.subjectNP-completenessen_US
dc.subjectBranch-and-bound algorithmsen_US
dc.subjectItemset miningen_US
dc.subjectEvolutionen_US
dc.subjectElementsen_US
dc.subjectGenesen_US
dc.subjectIdentificationen_US
dc.subjectDatabaseen_US
dc.subjectBioinformaticsen_US
dc.subjectBranch and bound methoden_US
dc.subjectCombinatorial optimizationen_US
dc.subjectComplex networksen_US
dc.subjectGene expressionen_US
dc.subjectSet theoryen_US
dc.subjectTranscriptionen_US
dc.subjectTranscription factorsen_US
dc.subjectCis-regulatory modulesen_US
dc.subjectBinding sitesen_US
dc.titleDiscovering cis-regulatory modules by optimizing barbecuesen_US
dc.typeArticleen_US
dspace.entity.typePublication

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
İsim:
330.pdf
Boyut:
899.55 KB
Biçim:
Adobe Portable Document Format
Açıklama:
Publisher's Version
İndir

Koleksiyon

Makale Koleksiyonu | Matematik Bölümü
Scopus İndeksli Yayınlar Koleksiyonu
WoS İndeksli Yayınlar Koleksiyonu