Discovering cis-regulatory modules by optimizing barbecues

Yükleniyor...
Küçük Resim

Tarih

2009-05-28

Dergi Başlığı

Dergi ISSN

Cilt Başlığı

Yayıncı

Elsevier Science Bv

Erişim Hakkı

info:eu-repo/semantics/closedAccess

Araştırma projeleri

Organizasyon Birimleri

Dergi sayısı

Özet

Gene 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.

Açıklama

This work was supported in part by the DFG Bioinformatics Initiative BIZ-6/1-2.

Anahtar Kelimeler

Gene regulation, Cis-regulatory modules (CRMs), Best barbecue problem, NP-completeness, Branch-and-bound algorithms, Itemset mining, Evolution, Elements, Genes, Identification, Database, Bioinformatics, Branch and bound method, Combinatorial optimization, Complex networks, Gene expression, Set theory, Transcription, Transcription factors, Cis-regulatory modules, Binding sites

Kaynak

Discrete Applied Mathematics

WoS Q Değeri

Q3

Scopus Q Değeri

Q2

Cilt

157

Sayı

10
SI

Künye

Mosig, 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.042