• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Discovering cis-regulatory modules by optimizing barbecues
【24h】

Discovering cis-regulatory modules by optimizing barbecues

机译：通过优化烧烤发现顺式调控模块

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：真核细胞中的基因表达受复杂的相互作用网络调节，其中转录因子及其在基因组DNA上的结合位点起决定性作用。由于转录因子很少（如果有的话）单独起作用，因此相互作用因子的结合位点通常紧密相邻地排列，形成所谓的顺式调节模块。即使知道各个结合位点，模块发现仍然是一个困难的组合问题，在这里我们将其形式化为“最佳烧烤问题”。它要求同时从K个彩色间隔排列中刺入最大数量的不同彩色间隔。这个几何问题原来是检测超图族中公共边的基本但尚未研究的组合优化问题，在这里我们将其决策版本显示为NP完全。由于其在生物学应用中的相关性，我们提出了适合于分析包含许多序列或许多结合位点的真实数据集的算法变异。基于由间隔安排诱发的集合系统，我们的问题设置可概括为发现由相应安排组成的非序列对象中的共定位项集的模式，或归纳共定位项的集合系统。实际上，我们的优化问题是对频繁项集挖掘的流行概念的概括。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号