Speeding up HMM algorithms for genetic linkage analysis via chain reductions of the state space Export

@article{citeulike:4698522, abstract = {We develop an hidden Markov model (HMM)-based algorithm for computing exact parametric and non-parametric linkage scores in larger pedigrees than was possible before. The algorithm is applicable whenever there are chains of persons in the pedigree with no genetic measurements and with unknown affection status. The algorithm is based on shrinking the state space of the HMM considerably using such chains. In a two g-degree cousins pedigree the reduction drops the state space from being exponential in g to being linear in g. For a Finnish family in which two affected children suffer from a rare cold-inducing sweating syndrome, we were able to reduce the state space by more than five orders of magnitude from 250 to 232. In another pedigree of state-space size of 227, used for a study of pituitary adenoma, the state space reduced by a factor of 8.5 and consequently exact linkage scores can now be computed, rather than approximated. Contact: dang@cs.technion.ac.il Supplementary information: Supplementary data are available at Bioinformatics online. 10.1093/bioinformatics/btp224}, author = {Geiger, Dan and Meek, Christopher and Wexler, Ydo}, citeulike-article-id = {4698522}, citeulike-linkout-0 = {http://dx.doi.org/10.1093/bioinformatics/btp224}, citeulike-linkout-1 = {http://bioinformatics.oxfordjournals.org/cgi/content/abstract/25/12/i196?rss=1}, citeulike-linkout-2 = {http://view.ncbi.nlm.nih.gov/pubmed/19477987}, citeulike-linkout-3 = {http://www.hubmed.org/display.cgi?uids=19477987}, day = {15}, doi = {10.1093/bioinformatics/btp224}, journal = {Bioinformatics}, keywords = {hmm, linkage, statistic}, month = {June}, number = {12}, pages = {i196--203}, posted-at = {2009-06-03 14:58:42}, priority = {2}, title = {Speeding up HMM algorithms for genetic linkage analysis via chain reductions of the state space}, url = {http://dx.doi.org/10.1093/bioinformatics/btp224}, volume = {25}, year = {2009} }

TY - JOUR ID - citeulike:4698522 L3 - citeulike-article-id:4698522 N2 - We develop an hidden Markov model (HMM)-based algorithm for computing exact parametric and non-parametric linkage scores in larger pedigrees than was possible before. The algorithm is applicable whenever there are chains of persons in the pedigree with no genetic measurements and with unknown affection status. The algorithm is based on shrinking the state space of the HMM considerably using such chains. In a two g-degree cousins pedigree the reduction drops the state space from being exponential in g to being linear in g. For a Finnish family in which two affected children suffer from a rare cold-inducing sweating syndrome, we were able to reduce the state space by more than five orders of magnitude from 250 to 232. In another pedigree of state-space size of 227, used for a study of pituitary adenoma, the state space reduced by a factor of 8.5 and consequently exact linkage scores can now be computed, rather than approximated. Contact: dang@cs.technion.ac.il Supplementary information: Supplementary data are available at Bioinformatics online. 10.1093/bioinformatics/btp224 IS - 12 JF - Bioinformatics EP - 203 TI - Speeding up HMM algorithms for genetic linkage analysis via chain reductions of the state space VL - 25 SP - i196 KW - hmm KW - linkage KW - statistic AU - Geiger, Dan AU - Meek, Christopher AU - Wexler, Ydo PY - 2009/06/15/ UR - http://dx.doi.org/10.1093/bioinformatics/btp224 ER -