{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:22Z","timestamp":1750308802648,"version":"3.41.0"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2011,5,1]],"date-time":"2011-05-01T00:00:00Z","timestamp":1304208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0635257","ccf1013110"],"award-info":[{"award-number":["CCF-0635257","ccf1013110"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["PGS M-377343-2009"],"award-info":[{"award-number":["PGS M-377343-2009"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2011,5]]},"abstract":"<jats:p>The development of cancer is largely driven by the gain or loss of subsets of the genome, promoting uncontrolled growth or disabling defenses against it. Denoising array-based Comparative Genome Hybridization (aCGH) data is an important computational problem central to understanding cancer evolution. In this article, we propose a new formulation of the denoising problem that we solve with a \u201cvanilla\u201d dynamic programming algorithm, which runs in<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>) units of time. Then, we propose two approximation techniques. Our first algorithm reduces the problem into a well-studied geometric problem, namely halfspace emptiness queries, and provides an \u03f5 additive approximation to the optimal objective value in \u00d5(<jats:italic>n<\/jats:italic><jats:sup>4\/3;+\u0394<\/jats:sup>log (U\/\u03f5)) time, where \u0394 is an arbitrarily small positive constant and<jats:italic>U<\/jats:italic>= max{#8730;C,(|<jats:italic>P<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub>|)<jats:sub><jats:italic>i<\/jats:italic>=1,\u2026,<jats:italic>n<\/jats:italic><\/jats:sub>} (<jats:italic>P<\/jats:italic>=(<jats:italic>P<\/jats:italic><jats:sub>1<\/jats:sub>,<jats:italic>P<\/jats:italic><jats:sub>2<\/jats:sub>, \u2026,<jats:italic>P<\/jats:italic><jats:italic><jats:sub>n<\/jats:sub><\/jats:italic>),<jats:italic>P<\/jats:italic><jats:italic><jats:sub>i<\/jats:sub><\/jats:italic>\u2208 \u211d, is the vector of the noisy aCGH measurements,<jats:italic>C<\/jats:italic>a normalization constant). The second algorithm provides a (1 \u00b1 \u03f5) approximation (multiplicative error) and runs in<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>log<jats:italic>n<\/jats:italic>\/\u03f5) time. The algorithm decomposes the initial problem into a small (logarithmic) number of Monge optimization subproblems that we can solve in linear time using existing techniques.<\/jats:p><jats:p>Finally, we validate our model on synthetic and real cancer datasets. Our method consistently achieves superior precision and recall to leading competitors on the data with ground truth. In addition, it finds several novel markers not recorded in the benchmarks but supported in the oncology literature.<\/jats:p>","DOI":"10.1145\/1963190.2063517","type":"journal-article","created":{"date-parts":[[2012,10,15]],"date-time":"2012-10-15T19:22:23Z","timestamp":1350328943000},"source":"Crossref","is-referenced-by-count":2,"title":["Approximation algorithms for speeding up dynamic programming and denoising aCGH data"],"prefix":"10.1145","volume":"16","author":[{"given":"Charalampos E.","family":"Tsourakakis","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria A.","family":"Tsiarli","sequence":"additional","affiliation":[{"name":"University of Pittsburgh"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gary L.","family":"Miller","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Russell","family":"Schwartz","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,12,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267816"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Agarwal P. K. and Erickson J. 1999. Geometric Range Searching and Its Relatives. http:\/\/theory.cs.uiuc.edu\/~jeffe\/pubs\/pdf\/survey-tr.pdf. Agarwal P. K. and Erickson J. 1999. Geometric Range Searching and Its Relatives. http:\/\/theory.cs.uiuc.edu\/~jeffe\/pubs\/pdf\/survey-tr.pdf.","DOI":"10.1090\/conm\/223\/03131"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100260"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/10515.10546"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/hmg\/ddg261"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","DOI":"10.1080\/01621459.1993.10594323","article-title":"A bayesian analysis for change point problems","volume":"88","author":"Barry D.","year":"1993","unstructured":"Barry , D. and Hartigan , J. 1993 . A bayesian analysis for change point problems . J. Amer. Stat. Assoc. 88 , 421, 309--319. Barry, D. and Hartigan, J. 1993. A bayesian analysis for change point problems. J. Amer. Stat. Assoc. 88, 421, 309--319.","journal-title":"J. Amer. Stat. Assoc."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644032"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/ajmg.a.30621"},{"volume-title":"Dynamic Programming","author":"Bellman R.","key":"e_1_2_1_9_1","unstructured":"Bellman , R. 2003. Dynamic Programming . Dover Publications , Mineola, NY . Bellman, R. 2003. Dynamic Programming. Dover Publications, Mineola, NY."},{"volume-title":"Dynamic Programming and Optimal Control","author":"Bertsekas D.","key":"e_1_2_1_10_1","unstructured":"Bertsekas , D. 2000. Dynamic Programming and Optimal Control . Athena Scientific , Nashua, NH . Bertsekas, D. 2000. Dynamic Programming and Optimal Control. Athena Scientific, Nashua, NH."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Bignell G. Huang J. Greshock J. Watt S. Butler A. West S. Grigorova M. Jones K. Wei W. Stratton M. Futreal A. Weber B. Shapero M. and Wooster R. 2004. High-resolution analysis of DNA copy number using oligonucleotide microarrays. Genome Res. 287--295. Bignell G. Huang J. Greshock J. Watt S. Butler A. West S. Grigorova M. Jones K. Wei W. Stratton M. Futreal A. Weber B. Shapero M. and Wooster R. 2004. High-resolution analysis of DNA copy number using oligonucleotide microarrays. Genome Res. 287--295.","DOI":"10.1101\/gr.2012304"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00103-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/ajmg.1320230307"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934990"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/323233.323248"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1078\/0344-0338-00423"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1038\/sj.onc.1208641"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.1999.6.37"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1089\/10665270050514936"},{"volume-title":"Proceedings of the IEEE International Conference on Bioinformatics & Biomedicine. IEEE","author":"Ding J.","key":"e_1_2_1_21_1","unstructured":"Ding , J. and Shah , S. P . 2010. Robust hidden semi-Markov modeling of array CGH data . In Proceedings of the IEEE International Conference on Bioinformatics & Biomedicine. IEEE , Los Alamitos, CA, 603--608. Ding, J. and Shah, S. P. 2010. Robust hidden semi-Markov modeling of array CGH data. In Proceedings of the IEEE International Conference on Bioinformatics & Biomedicine. IEEE, Los Alamitos, CA, 603--608."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti148"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21965"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146650"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146656"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmva.2004.02.008"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1959.tb01583.x"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132873"},{"key":"e_1_2_1_29_1","unstructured":"Guha S. Li Y. and Neuberg D. 2006. Bayesian hidden Markov modeling of array CGH data. Harvard University Working Paper 24. Guha S. Li Y. and Neuberg D. 2006. Bayesian hidden Markov modeling of array CGH data. Harvard University Working Paper 24."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360861"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023085825042"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/biostatistics\/kxi004"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti646"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth418"},{"volume-title":"Proceedings of the 24rd International Conference on Very Large Data Bases (VLDB'98)","author":"Jagadish H. V.","key":"e_1_2_1_35_1","unstructured":"Jagadish , H. V. , Koudas , N. , Muthukrishnan , S. , Poosala , V. , Sevcik , K. C. , and Torsten , S . 1998. Optimal histograms with quality guarantees . In Proceedings of the 24rd International Conference on Very Large Data Bases (VLDB'98) . Morgan Kaufmann, San Francisco, CA, 275--286. Jagadish, H. V., Koudas, N., Muthukrishnan, S., Poosala, V., Sevcik, K. C., and Torsten, S. 1998. Optimal histograms with quality guarantees. In Proceedings of the 24rd International Conference on Very Large Data Bases (VLDB'98). Morgan Kaufmann, San Francisco, CA, 275--286."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth355"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Kallioniemi A. Kallioniemi O. Sudar D. Rutovitz D. Gray J. Waldman F. and Pinkel D. 1992. Comparative genomic hybridization for molecular cytogenetic analysis of solid tumors. Science 258 5083 818--821. Kallioniemi A. Kallioniemi O. Sudar D. Rutovitz D. Gray J. Waldman F. and Pinkel D. 1992. Comparative genomic hybridization for molecular cytogenetic analysis of solid tumors. Science 258 5083 818--821.","DOI":"10.1126\/science.1359641"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1159\/000048779"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403009"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264289"},{"volume-title":"Seminumerical Algorithms","author":"Knuth D. E.","key":"e_1_2_1_41_1","unstructured":"Knuth , D. E. 1981. Seminumerical Algorithms . Addison-Wesley , Upper Saddle River, NJ. Knuth, D. E. 1981. Seminumerical Algorithms. Addison-Wesley, Upper Saddle River, NJ."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti611"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90016-R"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sigpro.2005.01.012"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1038\/sj.onc.1208304"},{"key":"e_1_2_1_46_1","first-page":"1721","article-title":"Etude des chromosomes somatiques de neuf enfants mongoliens","volume":"248","author":"Lejeune J.","year":"1959","unstructured":"Lejeune , J. , Gautier , M. , and Turpin , R. 1959 . Etude des chromosomes somatiques de neuf enfants mongoliens . Comptes Rendus Hebdomadaires des Seances de l'Academie des Sciences (Paris) 248 , 11, 1721 -- 1722 . Lejeune, J., Gautier, M., and Turpin, R. 1959. Etude des chromosomes somatiques de neuf enfants mongoliens. Comptes Rendus Hebdomadaires des Seances de l'Academie des Sciences (Paris) 248, 11, 1721--1722.","journal-title":"Comptes Rendus Hebdomadaires des Seances de l'Academie des Sciences (Paris)"},{"key":"e_1_2_1_47_1","first-page":"3098","article-title":"Trois ca de deletion partielle du bras court d'un chromosome 5","volume":"257","author":"Lejeune J.","year":"1963","unstructured":"Lejeune , J. , Lafourcade , J. , Berger , R. , Vialatta , J. , Boeswillwald , M. , Seringe , P. , and Turpin , R. 1963 . Trois ca de deletion partielle du bras court d'un chromosome 5 . Compte Rendus de l'Academie des Sciences (Paris) 257 , 3098 . Lejeune, J., Lafourcade, J., Berger, R., Vialatta, J., Boeswillwald, M., Seringe, P., and Turpin, R. 1963. Trois ca de deletion partielle du bras court d'un chromosome 5. Compte Rendus de l'Academie des Sciences (Paris) 257, 3098.","journal-title":"Compte Rendus de l'Academie des Sciences (Paris)"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/11415770_6"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185370"},{"key":"e_1_2_1_50_1","unstructured":"Monge G. 1781. Memoire sue la theorie des deblais et de remblais. Histoire de lAcademie Royale des Sciences de Paris 666--704. Monge G. 1781. Memoire sue la theorie des deblais et de remblais. Histoire de lAcademie Royale des Sciences de Paris 666--704."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth440"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ccr.2006.10.008"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.2353\/jmoldx.2006.060033"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1093\/biostatistics\/kxh008"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1158\/0008-5472.CAN-04-0756"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-6-27"},{"key":"e_1_2_1_57_1","doi-asserted-by":"crossref","unstructured":"Picard F. Robin S. Lebarbier E. and Daudin J. 2007. A segmentation\/clustering model for the analysis of array CGH data. Biometrics 63. Picard F. Robin S. Lebarbier E. and Daudin J. 2007. A segmentation\/clustering model for the analysis of array CGH data. Biometrics 63.","DOI":"10.1111\/j.1541-0420.2006.00729.x"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1038\/2524"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1038\/12640"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176343001"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl238"},{"volume-title":"Proceedings of RECOMB, 151--165","author":"Shi Y.","key":"e_1_2_1_62_1","unstructured":"Shi , Y. , Guo , F. , Wu , W. , and Xing , E. P . 2007. Gimscan: A new statistical method for analyzing whole-genome array CGH data . In Proceedings of RECOMB, 151--165 . Shi, Y., Guo, F., Wu, W., and Xing, E. P. 2007. Gimscan: A new statistical method for analyzing whole-genome array CGH data. In Proceedings of RECOMB, 151--165."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1038\/ng754"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1093\/biostatistics\/kxm013"},{"key":"e_1_2_1_65_1","first-page":"178","article-title":"Ontological enrichment of the Genes-to-Systems breast cancer database","volume":"46","author":"Viti F.","year":"2009","unstructured":"Viti , F. , Mosca , E. , Merelli , I. , Calabria , A. , Alfieri , R. , and Milanesi , L. 2009 . Ontological enrichment of the Genes-to-Systems breast cancer database . Commun. Comput. Inf. Sci. 46 , 178 -- 182 . Viti, F., Mosca, E., Merelli, I., Calabria, A., Alfieri, R., and Milanesi, L. 2009. Ontological enrichment of the Genes-to-Systems breast cancer database. Commun. Comput. Inf. Sci. 46, 178--182.","journal-title":"Commun. Comput. Inf. Sci."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1093\/biostatistics\/kxh017"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(86)90025-4"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti677"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1093\/biostatistics\/kxl035"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804691"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/0603055"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.genom.9.081307.164217"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1963190.2063517","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1963190.2063517","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:02Z","timestamp":1750278362000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1963190.2063517"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5]]},"references-count":72,"alternative-id":["10.1145\/1963190.2063517"],"URL":"https:\/\/doi.org\/10.1145\/1963190.2063517","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2011,5]]}}}