A model-based circular binary segmentation algorithm for the analysis of array CGH data.
A model-based circular binary segmentation algorithm for the analysis of array CGH data.
复制标题
DOI：
10.1186/1756-0500-4-394
复制
发表时间：
2011-10-10
影响因子：
1.8
通讯作者：
Chen Y
中科院分区：
文献类型：
--
作者：
Hsu FH;Chen HI;Tsai MH;Lai LC;Huang CC;Tu SH;Chuang EY;Chen Y
圆形二值分割（CBS）是一种基于排列的阵列比较基因组杂交（aCGH）数据分析算法。CBS通过使用最大t检验检测变化点来准确地分割数据；但是，利用排列来评估改变点的重要性会带来大量的计算负担。最近提出了一种利用混合方法和早期停止规则（混合CBS）来提高速度性能的实现方法。然而，时间分析表明，混合CBS的大部分计算时间仍然花在排列上。此外，混合方法提供的是意义上界或下界的近似值，而不是对变化点本身意义的近似值。我们开发了一种新的基于模型的算法，基于极值的CBS (eCBS)，它限制了排列，并在不损失准确性的情况下提供了鲁棒的结果。基于多种非正态假设，预先模拟了零假设下的数千个aCGH数据，并采用广义极值（GEV）分布建模了相应的最大值-t分布。建模结果将aCGH数据的特征与GEV参数相关联，构成查找表（eXtreme模型）。使用eXtreme模型，可以通过表查找过程以恒定的时间复杂度评估更改点的重要性。本研究开发了一种新的算法——eCBS。目前的eCBS实现在计算时间上一直优于混合CBS的4倍到20倍，而不损失精度。源代码、补充资料、补充图表和补充表格可在http://ntumaps.cgm.ntu.edu.tw/eCBSsupplementary上找到。
Circular Binary Segmentation (CBS) is a permutation-based algorithm for array Comparative Genomic Hybridization (aCGH) data analysis. CBS accurately segments data by detecting change-points using a maximal-t test; but extensive computational burden is involved for evaluating the significance of change-points using permutations. A recent implementation utilizing a hybrid method and early stopping rules (hybrid CBS) to improve the performance in speed was subsequently proposed. However, a time analysis revealed that a major portion of computation time of the hybrid CBS was still spent on permutation. In addition, what the hybrid method provides is an approximation of the significance upper bound or lower bound, not an approximation of the significance of change-points itself. We developed a novel model-based algorithm, extreme-value based CBS (eCBS), which limits permutations and provides robust results without loss of accuracy. Thousands of aCGH data under null hypothesis were simulated in advance based on a variety of non-normal assumptions, and the corresponding maximal-t distribution was modeled by the Generalized Extreme Value (GEV) distribution. The modeling results, which associate characteristics of aCGH data to the GEV parameters, constitute lookup tables (eXtreme model). Using the eXtreme model, the significance of change-points could be evaluated in a constant time complexity through a table lookup process. A novel algorithm, eCBS, was developed in this study. The current implementation of eCBS consistently outperforms the hybrid CBS 4× to 20× in computation time without loss of accuracy. Source codes, supplementary materials, supplementary figures, and supplementary tables can be found at http://ntumaps.cgm.ntu.edu.tw/eCBSsupplementary.