Discovering cis-regulatory modules by optimizing barbecues
Discovering cis-regulatory modules by optimizing barbecues
复制标题
通过优化烧烤发现顺式调节模块
DOI：
10.1016/j.dam.2008.06.042
复制
发表时间：
2009-05
影响因子：
1.1
通讯作者：
Prohaska, Sonja J.
中科院分区：
文献类型：
--
作者：
Mosig, Axel;Biyikoglu, Türker;Stadler, Peter F.;Prohaska, Sonja J.
真核细胞中的基因表达受复杂的相互作用网络的调控，其中转录因子及其在基因组DNA上的结合位点起决定性作用。由于转录因子很少单独起作用，相互作用因子的结合位点通常紧密排列，形成所谓的顺式调控模块。即使当单个结合位点是已知的，模块发现仍然是一个很难的组合问题，我们在这里正式的最佳烧烤问题。它要求从K个有色区间的排列中同时刺入最大数量的不同有色区间。这个几何问题原来是一个基本的，但以前未研究过的组合优化问题，检测共同的边缘在一个家庭的超图，一个决定的版本，我们在这里显示是NP-完全的。由于其在生物应用中的相关性，我们提出了算法的变化，适合于分析的真实的数据集，包括许多序列或许多结合位点。基于区间安排诱导的集合系统，我们的问题设置推广到发现非顺序对象中的共定位项集的模式，这些模式由相应的安排或诱导共定位项集系统组成。事实上，我们的优化问题是一个普遍的概念，频繁项集挖掘的推广。
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.
登录
查看更多内容
影响因子：
12.3
作者：
Berman BP;Pfeiffer BD;Laverty TR;Salzberg SL;Rubin GM;Eisen MB;Celniker SE
通讯作者：
Celniker SE
影响因子：
5.8
作者：
A. Mosig;P. Menzel;P. Stadler
通讯作者：
A. Mosig;P. Menzel;P. Stadler
影响因子：
4.1
作者：
E. Davidson
通讯作者：
E. Davidson
影响因子：
5.8
作者：
Aerts, S;Van Loo, P;De Moor, B
通讯作者：
De Moor, B
影响因子：
14.9
作者：
Blanchette, M;Tompa, M
通讯作者：
Tompa, M