{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T19:10:13Z","timestamp":1740165013109,"version":"3.37.3"},"reference-count":42,"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":2315,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Association analysis is the method of choice for studying complex multifactorial diseases. The premise of this method is that affected persons contain some common genomic regions with similar SNP alleles and such areas will be found in this analysis. An important disadvantage of GWA studies is that it does not distinguish between genomic areas that are inherited from a common ancestor [identical by descent (IBD)] and areas that are identical merely by state [identical by state (IBS)]. Clearly, areas that can be marked with higher probability as IBD and have the same correlation with the disease status of identical areas that are more probably only IBS, are better candidates to be causative, and yet this distinction is not encoded in standard association analysis.<\/jats:p><jats:p>Results: We develop a factorial hidden Markov model-based algorithm for computing genome-wide IBD sharing. The algorithm accepts as input SNP data of measured individuals and estimates the probability of IBD at each locus for every pair of individuals. For two g-degree relatives, when g\u22658, the computation yields a precision of IBD tagging of over 50% higher than previous methods for 95% recall. Our algorithm uses a first-order Markovian model for the linkage disequilibrium process and employs a reduction of the state space of the inheritance vector from being exponential in g to quadratic. The higher accuracy along with the reduced time complexity marks our method as a feasible means for IBD mapping in practical scenarios.<\/jats:p><jats:p>Availability: A software implementation, called IBDMAP, is freely available at http:\/\/bioinfo.cs.technion.ac.il\/IBDmap.<\/jats:p><jats:p>Contact: \u00a0sberco@gmail.com<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq204","type":"journal-article","created":{"date-parts":[[2010,6,7]],"date-time":"2010-06-07T07:28:13Z","timestamp":1275895693000},"page":"i175-i182","source":"Crossref","is-referenced-by-count":22,"title":["Estimating genome-wide IBD sharing from SNP data via an efficient hidden Markov model of LD with application to gene mapping"],"prefix":"10.1093","volume":"26","author":[{"given":"Sivan","family":"Bercovici","sequence":"first","affiliation":[{"name":"1 Technion-Israel Institute of Technology, Computer Science Department Haifa, 32000 Israel and 2 Microsoft Research, Redmond, WA 98052, USA"}]},{"given":"Christopher","family":"Meek","sequence":"additional","affiliation":[{"name":"1 Technion-Israel Institute of Technology, Computer Science Department Haifa, 32000 Israel and 2 Microsoft Research, Redmond, WA 98052, USA"}]},{"given":"Ydo","family":"Wexler","sequence":"additional","affiliation":[{"name":"1 Technion-Israel Institute of Technology, Computer Science Department Haifa, 32000 Israel and 2 Microsoft Research, Redmond, WA 98052, USA"}]},{"given":"Dan","family":"Geiger","sequence":"additional","affiliation":[{"name":"1 Technion-Israel Institute of Technology, Computer Science Department Haifa, 32000 Israel and 2 Microsoft Research, Redmond, WA 98052, USA"},{"name":"1 Technion-Israel Institute of Technology, Computer Science Department Haifa, 32000 Israel and 2 Microsoft Research, Redmond, WA 98052, USA"}]}],"member":"286","published-online":{"date-parts":[[2010,6,1]]},"reference":[{"key":"2023012508041841000_B1","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1086\/497345","article-title":"Handling marker-marker linkage disequilibrium: pedigree analysis with clustered markers","volume":"77","author":"Abecasis","year":"2005","journal-title":"Am. J. Hum. Genet."},{"key":"2023012508041841000_B2","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":"2023012508041841000_B3","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1534\/genetics.104.036699","article-title":"Quantitative traits loci analysis using the false discovery rate","volume":"171","author":"Benjamini","year":"2005","journal-title":"Genetics"},{"key":"2023012508041841000_B4","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1089\/cmb.2009.0105","article-title":"Inferring ancestries efficiently in admixed populations with linkage disequilibrium","volume":"16","author":"Bercovici","year":"2009","journal-title":"J. Comput. Biol."},{"key":"2023012508041841000_B5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/tpbi.2002.1583","article-title":"On reducing the statespace of hidden markov models for the identity by descent process","volume":"62","author":"Browning","year":"2002","journal-title":"Theor. Popul. Biol."},{"key":"2023012508041841000_B6","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0168-9525(03)00022-2","article-title":"Using haplotype blocks to map human complex trait loci","volume":"19","author":"Cardon","year":"2003","journal-title":"Trends Genet."},{"key":"2023012508041841000_B7","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1038\/nature02623","article-title":"Mapping complex disease loci in whole-genome association studies","volume":"429","author":"Carlson","year":"2004","journal-title":"Nature"},{"key":"2023012508041841000_B8","first-page":"252","article-title":"Faster sequential genetic linkage computations","volume":"53","author":"Cottingham","year":"1993","journal-title":"Am. J. Hum. Genet."},{"key":"2023012508041841000_B9","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":"Proceedings of the NATO Advanced Study Institute on Learning in graphical models","author":"Dechter","year":"1998"},{"key":"2023012508041841000_B10","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."},{"key":"2023012508041841000_B11","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1101\/gr.072785.107","article-title":"Increasing power in association studies by using linkage disequilibrium structure and molecular function as prior information","volume":"18","author":"Eskin","year":"2008","journal-title":"Genome Res."},{"issue":"Suppl. 1","key":"2023012508041841000_B12","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":"2023012508041841000_B13","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1038\/nature06258","article-title":"A second generation human haplotype map of over 3.1 million snps","volume":"449","author":"Frazer","year":"2007","journal-title":"Nature"},{"key":"2023012508041841000_B14","doi-asserted-by":"crossref","first-page":"i196","DOI":"10.1093\/bioinformatics\/btp224","article-title":"Speeding up HMM algorithms for genetic linkage analysis via chain reductions of the state space","volume":"25","author":"Geiger","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012508041841000_B15","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1023\/A:1007425814087","article-title":"Factorial hidden Markov models","volume":"29","author":"Ghahramani","year":"1997","journal-title":"Mach. Learn."},{"issue":"Suppl. 1","key":"2023012508041841000_B16","doi-asserted-by":"crossref","first-page":"i137","DOI":"10.1093\/bioinformatics\/bth907","article-title":"High density linkage disequilibrium mapping using models of haplotype block variation","volume":"20","author":"Greenspan","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012508041841000_B17","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1038\/ng1005-1015","article-title":"Allegro version 2","volume":"37","author":"Gudbjartsson","year":"2005","journal-title":"Nat. Genet."},{"key":"2023012508041841000_B18","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":"2023012508041841000_B19","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1038\/nbt0309-255","article-title":"Maximizing power in association studies","volume":"27","author":"Halperin","year":"2009","journal-title":"Nat. Biotecmol."},{"issue":"Suppl. 1","key":"2023012508041841000_B20","doi-asserted-by":"crossref","first-page":"i195","DOI":"10.1093\/bioinformatics\/bti1021","article-title":"Tag SNP selection in genotype data for maximizing SNP prediction accuracy","volume":"21","author":"Halperin","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012508041841000_B21","doi-asserted-by":"crossref","first-page":"e1000456","DOI":"10.1371\/journal.pgen.1000456","article-title":"Rapid and accurate multiple testing correction and power estimation for millions of correlated markers","volume":"5","author":"Han","year":"2009","journal-title":"PloS Genet."},{"key":"2023012508041841000_B22","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/11599128_9","article-title":"Genetic linkage analysis, algorithms and their implementation","volume":"3737","author":"Ingolfsdottir","year":"2005","journal-title":"Trans. Comput. Syst. Biol."},{"key":"2023012508041841000_B23","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":"2023012508041841000_B24","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":"2023012508041841000_B25","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":"2023012508041841000_B26","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":"2023012508041841000_B27","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":"2023012508041841000_B28","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198522195.001.0001","volume-title":"Graphical Models.","author":"Lauritzen","year":"1996"},{"key":"2023012508041841000_B29","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. Roy. Stat. Soc. Series B stat. Methodol."},{"key":"2023012508041841000_B30","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":"2023012508041841000_B31","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":"2023012508041841000_B32","doi-asserted-by":"crossref","DOI":"10.56021\/9780801861406","volume-title":"Analysis of Human Genetic Linkage.","author":"Ott","year":"1999"},{"volume-title":"Probabilistic Reasoning in Intelligent Systems.","year":"1988","author":"Pearl","key":"2023012508041841000_B33"},{"key":"2023012508041841000_B34","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1038\/ng1816","article-title":"Evaluating and improving power in whole genome association studies using fixed marker sets","volume":"38","author":"Peer","year":"2006","journal-title":"Nat. Genet."},{"key":"2023012508041841000_B35","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1002\/gepi.20303","article-title":"Estimation of the multiple testing burden for genomewide association studies of nearly all common variants","volume":"32","author":"Peer","year":"2008","journal-title":"Genet. Epidemiol."},{"key":"2023012508041841000_B36","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1086\/519795","article-title":"Plink: a tool set for whole-genome association and population-based linkage analyses","volume":"81","author":"Purcell","year":"2007","journal-title":"Am. J. Hum. Genet."},{"key":"2023012508041841000_B37","first-page":"4","article-title":"An introduction to hidden Markov models","author":"Rabiner","year":"1986","journal-title":"IEEE Acoust. Speech sign. Process. Mag."},{"key":"2023012508041841000_B38","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1214\/aos\/1176344136","article-title":"Estimating the dimension of a model","volume":"6","author":"Schwarz","year":"1978","journal-title":"Ann. Stat."},{"key":"2023012508041841000_B39","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":"2023012508041841000_B40","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":"2023012508041841000_B41","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":"2023012508041841000_B42","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1038\/nrg1522","article-title":"Genome-wide association studies: theoretical and practical concerns","volume":"6","author":"Wang","year":"2005","journal-title":"Nat. Rev. Genet."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/12\/i175\/48855554\/bioinformatics_26_12_i175.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/12\/i175\/48855554\/bioinformatics_26_12_i175.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T18:29:01Z","timestamp":1740162541000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/12\/i175\/284619"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,1]]},"references-count":42,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2010,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq204","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"type":"electronic","value":"1367-4811"},{"type":"print","value":"1367-4803"}],"subject":[],"published-other":{"date-parts":[[2010,6,15]]},"published":{"date-parts":[[2010,6,1]]}}}