Fast MCMC sampling for hidden markov models to determine copy number variations
<p>Abstract</p> <p>Background</p> <p>Hidden Markov Models (HMM) are often used for analyzing Comparative Genomic Hybridization (CGH) data to identify chromosomal aberrations or copy number variations by segmenting observation sequences. For efficiency reasons the parame...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2011-11-01
|
| Series: | BMC Bioinformatics |
| Online Access: | http://www.biomedcentral.com/1471-2105/12/428 |
| _version_ | 1828352038958792704 |
|---|---|
| author | Mahmud Md Pavel Schliep Alexander |
| author_facet | Mahmud Md Pavel Schliep Alexander |
| author_sort | Mahmud Md Pavel |
| collection | DOAJ |
| description | <p>Abstract</p> <p>Background</p> <p>Hidden Markov Models (HMM) are often used for analyzing Comparative Genomic Hybridization (CGH) data to identify chromosomal aberrations or copy number variations by segmenting observation sequences. For efficiency reasons the parameters of a HMM are often estimated with maximum likelihood and a segmentation is obtained with the Viterbi algorithm. This introduces considerable uncertainty in the segmentation, which can be avoided with Bayesian approaches integrating out parameters using Markov Chain Monte Carlo (MCMC) sampling. While the advantages of Bayesian approaches have been clearly demonstrated, the likelihood based approaches are still preferred in practice for their lower running times; datasets coming from high-density arrays and next generation sequencing amplify these problems.</p> <p>Results</p> <p>We propose an approximate sampling technique, inspired by compression of discrete sequences in HMM computations and by <it>kd</it>-trees to leverage spatial relations between data points in typical data sets, to speed up the MCMC sampling.</p> <p>Conclusions</p> <p>We test our approximate sampling method on simulated and biological ArrayCGH datasets and high-density SNP arrays, and demonstrate a speed-up of 10 to 60 respectively 90 while achieving competitive results with the state-of-the art Bayesian approaches.</p> <p><it>Availability: </it>An implementation of our method will be made available as part of the open source GHMM library from <url>http://ghmm.org</url>.</p> |
| first_indexed | 2024-04-14T01:49:05Z |
| format | Article |
| id | doaj.art-d06a31169b5d4267b606f75d803acdc3 |
| institution | Directory Open Access Journal |
| issn | 1471-2105 |
| language | English |
| last_indexed | 2024-04-14T01:49:05Z |
| publishDate | 2011-11-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Bioinformatics |
| spelling | doaj.art-d06a31169b5d4267b606f75d803acdc32022-12-22T02:19:26ZengBMCBMC Bioinformatics1471-21052011-11-0112142810.1186/1471-2105-12-428Fast MCMC sampling for hidden markov models to determine copy number variationsMahmud Md PavelSchliep Alexander<p>Abstract</p> <p>Background</p> <p>Hidden Markov Models (HMM) are often used for analyzing Comparative Genomic Hybridization (CGH) data to identify chromosomal aberrations or copy number variations by segmenting observation sequences. For efficiency reasons the parameters of a HMM are often estimated with maximum likelihood and a segmentation is obtained with the Viterbi algorithm. This introduces considerable uncertainty in the segmentation, which can be avoided with Bayesian approaches integrating out parameters using Markov Chain Monte Carlo (MCMC) sampling. While the advantages of Bayesian approaches have been clearly demonstrated, the likelihood based approaches are still preferred in practice for their lower running times; datasets coming from high-density arrays and next generation sequencing amplify these problems.</p> <p>Results</p> <p>We propose an approximate sampling technique, inspired by compression of discrete sequences in HMM computations and by <it>kd</it>-trees to leverage spatial relations between data points in typical data sets, to speed up the MCMC sampling.</p> <p>Conclusions</p> <p>We test our approximate sampling method on simulated and biological ArrayCGH datasets and high-density SNP arrays, and demonstrate a speed-up of 10 to 60 respectively 90 while achieving competitive results with the state-of-the art Bayesian approaches.</p> <p><it>Availability: </it>An implementation of our method will be made available as part of the open source GHMM library from <url>http://ghmm.org</url>.</p>http://www.biomedcentral.com/1471-2105/12/428 |
| spellingShingle | Mahmud Md Pavel Schliep Alexander Fast MCMC sampling for hidden markov models to determine copy number variations BMC Bioinformatics |
| title | Fast MCMC sampling for hidden markov models to determine copy number variations |
| title_full | Fast MCMC sampling for hidden markov models to determine copy number variations |
| title_fullStr | Fast MCMC sampling for hidden markov models to determine copy number variations |
| title_full_unstemmed | Fast MCMC sampling for hidden markov models to determine copy number variations |
| title_short | Fast MCMC sampling for hidden markov models to determine copy number variations |
| title_sort | fast mcmc sampling for hidden markov models to determine copy number variations |
| url | http://www.biomedcentral.com/1471-2105/12/428 |
| work_keys_str_mv | AT mahmudmdpavel fastmcmcsamplingforhiddenmarkovmodelstodeterminecopynumbervariations AT schliepalexander fastmcmcsamplingforhiddenmarkovmodelstodeterminecopynumbervariations |