A faster circular binary segmentation algorithm for the analysis of array CGH data Journal Article
| Authors: | Venkatraman, E. S.; Olshen, A. B. |
| Article Title: | A faster circular binary segmentation algorithm for the analysis of array CGH data |
| Abstract: | Motivation: Array CGH technologies enable the simultaneous measurement of DNA copy number for thousands of sites on a genome. We developed the circular binary segmentation (CBS) algorithm to divide the genome into regions of equal copy number. The algorithm tests for change-points using a maximal t-statistic with a permutation reference distribution to obtain the corresponding P-value. The number of computations required for the maximal test statistic is O(N2), where N is the number of markers. This makes the full permutation approach computationally prohibitive for the newer arrays that contain tens of thousands markers and highlights the need for a faster algorithm. Results: We present a hybrid approach to obtain the P-value of the test statistic in linear time. We also introduce a rule for stopping early when there is strong evidence for the presence of a change. We show through simulations that the hybrid approach provides a substantial gain in speed with only a negligible loss in accuracy and that the stopping rule further increases speed. We also present the analyses of array CGH data from breast cancer cell lines to show the impact of the new approaches on the analysis of real data. © 2007 Oxford University Press. |
| Keywords: | controlled study; human cell; accuracy; breast cancer; statistics; cancer cell culture; algorithms; time factors; simulation; statistical significance; dna; algorithm; sequence alignment; oligonucleotide array sequence analysis; data analysis; genome; dna microarray; gene dosage; software; comparative genomic hybridization; chromosome mapping; sequence analysis, dna; programming languages |
| Journal Title: | Bioinformatics |
| Volume: | 23 |
| Issue: | 6 |
| ISSN: | 1367-4803 |
| Publisher: | Oxford University Press |
| Date Published: | 2007-03-15 |
| Start Page: | 657 |
| End Page: | 663 |
| Language: | English |
| DOI: | 10.1093/bioinformatics/btl646 |
| PUBMED: | 17234643 |
| PROVIDER: | scopus |
| DOI/URL: | |
| Notes: | --- - "Cited By (since 1996): 176" - "Export Date: 17 November 2011" - "CODEN: BOINF" - "Source: Scopus" |
Altmetric
Citation Impact
BMJ Impact Analytics
Related MSK Work