Fast Westfall-Young permutation procedure for combinatorial regulation discovery
Fast Westfall-Young permutation procedure for combinatorial regulation discovery
复制标题
用于组合调节发现的快速 Westfall-Young 排列程序
DOI：
10.1109/bibm.2013.6732479
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Jun Sese
中科院分区：
文献类型：
--
作者：
Aika Terada ; Koji Tsuda ; Jun Sese
三种或三种以上的转录因子经常一起工作，而组合调控在细胞机械中是必不可少的。然而，由于多重测试过程的必要性，不可能发现统计上有意义的Tf结合基序集。为了提高常用的Bonferroni校正或其改进方法，如Holm法、Westfall-Young排列法(WY法)的灵敏度，常采用WY法。然而，由于计算时间非常长，很少有研究使用WY程序来发现基序的组合效应。在本文中，我们提出了一种有效的分枝定界算法来执行WY过程来枚举统计上有意义的基序组合。当我们使用WY过程进行组合规则发现时，从每个排列的数据集中寻找最小P值耗费了大量的时间。我们发现，有可能达到最小P值的组合在数据集中出现的频率高于阈值。这一性质使得频繁项集挖掘算法能够有效地选择候选对象以获得最小P值。我们使用酵母和人类转录组数据集的演示表明，所提出的算法比WY过程快几个数量级，即使考虑到任何组合，实际上也可以列出统计上有意义的基序组合。
Three or more transcription factors (TFs) often work together, and the combinatorial regulations are essential in cellular machinery. However, it is impossible to discover statistically significant sets of TF binding motifs due to the necessity of the multiple testing procedure. To improve the sensitivity of widely used Bonferroni correction or its modified methods, such as Holm procedure, Westfall-Young permutation procedure (WY-procedure) has often been applied. However, few studies have used WY-procedure for the discoveries of the combinatorial effects of the motifs because of the extremely large computational time. In this paper, we propose an efficient branch-and-bound algorithm to perform WY-procedure to enumerate statistically significant motif combinations. When we use WY-procedure for the combinatorial regulation discovery, finding the minimum P-value from each permuted dataset consumes an enormous amount of time. We show that a combination that has the possibility to achieve the minimum P-value appears with high frequency over the threshold in dataset. This property enables a frequent itemset mining algorithm to efficiently select the candidates to achieve the minimum P-value. Our demonstrations using yeast and human transcriptome datasets show that the proposed algorithm is orders-of-magnitude faster than WY-procedure, and can practically list statistically significant motif combinations even when any combinations are considered.