{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:29:20Z","timestamp":1773271760248,"version":"3.50.1"},"reference-count":27,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2685,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p><jats:p>Contact: \u00a0dang@cs.technion.ac.il<\/jats:p><jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp224","type":"journal-article","created":{"date-parts":[[2009,5,28]],"date-time":"2009-05-28T15:48:54Z","timestamp":1243525734000},"page":"i196-i203","source":"Crossref","is-referenced-by-count":12,"title":["Speeding up HMM algorithms for genetic linkage analysis via chain reductions of the state space"],"prefix":"10.1093","volume":"25","author":[{"given":"Dan","family":"Geiger","sequence":"first","affiliation":[{"name":"1 Computer Science Department, Technion-Israel Institute of Technology, Haifa 32000, Israel and 2Microsoft Research, Redmond, WA 98052, USA"}]},{"given":"Christopher","family":"Meek","sequence":"additional","affiliation":[{"name":"1 Computer Science Department, Technion-Israel Institute of Technology, Haifa 32000, Israel and 2Microsoft Research, Redmond, WA 98052, USA"}]},{"given":"Ydo","family":"Wexler","sequence":"additional","affiliation":[{"name":"1 Computer Science Department, Technion-Israel Institute of Technology, Haifa 32000, Israel and 2Microsoft Research, Redmond, WA 98052, USA"}]}],"member":"286","published-online":{"date-parts":[[2009,5,27]]},"reference":[{"key":"2023013112021797000_B1","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1038\/ng786","article-title":"Merlin-rapid analysis of dense genetic maps using sparse gene flow trees","volume":"30","author":"Abecasis","year":"2002","journal-title":"Nat. Genet."},{"key":"2023013112021797000_B2","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1016\/j.ajhg.2007.12.016","article-title":"Multipoint approximations of identity-by-descent probabilities for accurate linkage analysis of distantly related individuals","volume":"82","author":"Albers","year":"2008","journal-title":"Am. J. Hum. Genet."},{"key":"2023013112021797000_B3","first-page":"252","article-title":"Faster sequential genetic linkage computations","volume":"53","author":"Cottingham","year":"1993","journal-title":"Am. J. Hum. Genet."},{"key":"2023013112021797000_B4","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-94-011-5014-9_4","article-title":"Bucket elimination: a unifying framework for probabilistic inference","volume-title":"Learning in Graphical Models.","author":"Dechter","year":"1998"},{"key":"2023013112021797000_B5","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1159\/000152448","article-title":"A general model for the analysis of pedigree data","volume":"21","author":"Elston","year":"1971","journal-title":"Hum. Hered."},{"issue":"Suppl. 1","key":"2023013112021797000_B6","doi-asserted-by":"crossref","first-page":"S189","DOI":"10.1093\/bioinformatics\/18.suppl_1.S189","article-title":"Exact genetic linkage computations for general pedigrees","volume":"18","author":"Fishelson","year":"2002","journal-title":"Bioinformatics"},{"key":"2023013112021797000_B7","article-title":"Factorial hidden Markov models","volume-title":"Machine Learning.","author":"Ghahramani","year":"1997"},{"key":"2023013112021797000_B8","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1038\/75514","article-title":"Allegro, a new computer program for multipoint linkage analysis","volume":"25","author":"Gudbjartsson","year":"2000","journal-title":"Nat. Genet."},{"key":"2023013112021797000_B9","first-page":"1015","article-title":"Allegro version 2","volume":"37","author":"Gudbjartsson","year":"2005","journal-title":"Stat. Sci."},{"key":"2023013112021797000_B10","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/11599128_9","article-title":"Genetic linkage analysis, algorithms and their implementation","author":"Ingolfsdottir","year":"2005","journal-title":"Trans. Comput. Syst. Biol."},{"key":"2023013112021797000_B11","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1086\/346120","article-title":"Cold-induced sweating syndrome is caused by mutations in the CRLF1 Gene","volume":"72","author":"Knappskog","year":"2003","journal-title":"Am. J. Hum. Genet."},{"key":"2023013112021797000_B12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1089\/cmb.1998.5.1","article-title":"Faster multipoint linkage analysis using Fourier transform","volume":"5","author":"Kruglyak","year":"1998","journal-title":"J. Comput. Biol."},{"key":"2023013112021797000_B13","first-page":"519","article-title":"Rapid multipoint linkage analysis of recessive traits in nuclear families including homozygosity mapping","volume":"56","author":"Kruglyak","year":"1995","journal-title":"Am. J. Hum. Genet."},{"key":"2023013112021797000_B14","first-page":"1347","article-title":"Parametric and nonparametric linkage analysis: a unified multipoint approach","volume":"58","author":"Kruglyak","year":"1996","journal-title":"Am. J. Hum. Genet."},{"key":"2023013112021797000_B15","doi-asserted-by":"crossref","first-page":"2363","DOI":"10.1073\/pnas.84.8.2363","article-title":"Construction of multilocus genetic maps in humans","volume":"84","author":"Lander","year":"1987","journal-title":"Proc. Natl Acad. Sci."},{"key":"2023013112021797000_B16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2739-5","volume-title":"Mathematical and Statistical Methods for Genetic Analysis.","author":"Lange","year":"1997"},{"key":"2023013112021797000_B17","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1111\/j.2517-6161.1988.tb01721.x","article-title":"Local computations with probabilities on graphical structures and their application to expert systems (with discussion)","volume":"50","author":"Lauritzen","year":"1988","journal-title":"J. R. Stat. Soc. Ser. B"},{"key":"2023013112021797000_B18","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198522195.001.0001","volume-title":"Graphical Models.","author":"Lauritzen","year":"1996"},{"key":"2023013112021797000_B19","doi-asserted-by":"crossref","first-page":"963","DOI":"10.1086\/319507","article-title":"Efficient multipoint linkage analysis through reduction of inheritance space","volume":"68","author":"Markianos","year":"2001","journal-title":"Am. J. Hum. Genet."},{"key":"2023013112021797000_B20","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1038\/ng1295-402","article-title":"The VITESSE algorithm for rapid exact multilocus linkage analysis via genotype set-recoding and fuzzy inheritance","volume":"11","author":"O'Connell","year":"1995","journal-title":"Nat. Genet."},{"key":"2023013112021797000_B21","doi-asserted-by":"crossref","DOI":"10.56021\/9780801861406","volume-title":"Analysis of Human Genetic Linkage.","author":"Ott","year":"1999"},{"key":"2023013112021797000_B22","volume-title":"Probabilistic Reasoning in Intelligent Systems.","author":"Pearl","year":"1988"},{"key":"2023013112021797000_B23","first-page":"415","article-title":"An introduction to Hidden Markov models","author":"Rabiner","year":"1986","journal-title":"IEEE ASSP Mag."},{"key":"2023013112021797000_B24","doi-asserted-by":"crossref","first-page":"922","DOI":"10.1086\/504158","article-title":"Online system for faster multipoint linkage analysis via parallel execution on thousands of personal computers","volume":"78","author":"Silberstein","year":"2006","journal-title":"Am. J. Hum. Genet."},{"key":"2023013112021797000_B25","first-page":"1323","article-title":"Descent graphs in pedigree analysis: applications to haplotyping, location scores, and marker sharing statistics","volume":"58","author":"Sobel","year":"1996","journal-title":"Am. J. Hum. Genet."},{"key":"2023013112021797000_B26","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1214\/ss\/1177010381","article-title":"Monte Carlo likelihood in genetic mapping","volume":"9","author":"Thompson","year":"1994","journal-title":"Stat. Sci."},{"key":"2023013112021797000_B27","doi-asserted-by":"crossref","first-page":"1228","DOI":"10.1126\/science.1126100","article-title":"Pituitary Adenoma predisposition caused by germline mutations in the AIP Gene","volume":"312","author":"Vierimaa","year":"2006","journal-title":"Science"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/12\/i196\/48994866\/bioinformatics_25_12_i196.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/12\/i196\/48994866\/bioinformatics_25_12_i196.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,9]],"date-time":"2025-02-09T19:02:54Z","timestamp":1739127774000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/12\/i196\/191738"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,27]]},"references-count":27,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2009,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp224","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,6,15]]},"published":{"date-parts":[[2009,5,27]]}}}