{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T07:57:35Z","timestamp":1773734255751,"version":"3.50.1"},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Most existing identity-by-descent (IBD) detection methods only consider haplotype pairs; less attention has been paid to considering multiple haplotypes simultaneously, even though IBD is an equivalence relation on haplotypes that partitions a set of haplotypes into IBD clusters. Multiple-haplotype IBD clusters may have advantages over pairwise IBD in some applications, such as IBD mapping. Existing methods for detecting multiple-haplotype IBD clusters are often computationally expensive and unable to handle large samples with thousands of haplotypes.<\/jats:p>\n               <jats:p>Results: We present a clustering method, efficient multiple-IBD, which uses pairwise IBD segments to infer multiple-haplotype IBD clusters. It expands clusters from seed haplotypes by adding qualified neighbors and extends clusters across sliding windows in the genome. Our method is an order of magnitude faster than existing methods and has comparable performance with respect to the quality of clusters it uncovers. We further investigate the potential application of multiple-haplotype IBD clusters in association studies by testing for association between multiple-haplotype IBD clusters and low-density lipoprotein cholesterol in the Northern Finland Birth Cohort. Using our multiple-haplotype IBD cluster approach, we found an association with a genomic interval covering the PCSK9 gene in these data that is missed by standard single-marker association tests. Previously published studies confirm association of PCSK9 with low-density lipoprotein.<\/jats:p>\n               <jats:p>Availability and implementation: Source code is available under the GNU Public License http:\/\/cs.au.dk\/~qianyuxx\/EMI\/.<\/jats:p>\n               <jats:p>Contact: \u00a0qianyuxx@gmail.com<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt734","type":"journal-article","created":{"date-parts":[[2013,12,21]],"date-time":"2013-12-21T03:17:47Z","timestamp":1387595867000},"page":"915-922","source":"Crossref","is-referenced-by-count":13,"title":["Efficient clustering of identity-by-descent between multiple individuals"],"prefix":"10.1093","volume":"30","author":[{"given":"Yu","family":"Qian","sequence":"first","affiliation":[{"name":"1 Bioinformatics Research Center, Aarhus Universitet, 8000C Aarhus, Denmark, 2Department of Biostatistics and 3Division of Medical Genetics, Department of Medicine, University of Washington, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brian L.","family":"Browning","sequence":"additional","affiliation":[{"name":"1 Bioinformatics Research Center, Aarhus Universitet, 8000C Aarhus, Denmark, 2Department of Biostatistics and 3Division of Medical Genetics, Department of Medicine, University of Washington, Seattle, WA, USA"},{"name":"1 Bioinformatics Research Center, Aarhus Universitet, 8000C Aarhus, Denmark, 2Department of Biostatistics and 3Division of Medical Genetics, Department of Medicine, University of Washington, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharon R.","family":"Browning","sequence":"additional","affiliation":[{"name":"1 Bioinformatics Research Center, Aarhus Universitet, 8000C Aarhus, Denmark, 2Department of Biostatistics and 3Division of Medical Genetics, Department of Medicine, University of Washington, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2013,12,19]]},"reference":[{"key":"2023012710454040700_btt734-B1","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1534\/genetics.110.113977","article-title":"Natural selection and the distribution of identity-by-descent in the human genome","volume":"186","author":"Albrechtsen","year":"2010","journal-title":"Genetics"},{"key":"2023012710454040700_btt734-B2","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1146\/annurev-genet-110711-155534","article-title":"Identity by descent between distant relatives: detection and applications","volume":"46","author":"Browning","year":"2012","journal-title":"Ann. Rev. Genet."},{"key":"2023012710454040700_btt734-B3","doi-asserted-by":"crossref","first-page":"1521","DOI":"10.1534\/genetics.111.136937","article-title":"Detecting rare variant associations by identity-by-descent mapping in case-control studies","volume":"190","author":"Browning","year":"2012","journal-title":"Genetics"},{"key":"2023012710454040700_btt734-B4","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1534\/genetics.113.150029","article-title":"Improving the accuracy and efficiency of identity by descent detection in population data","volume":"194","author":"Browning","year":"2013","journal-title":"Genetics"},{"key":"2023012710454040700_btt734-B5","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s00439-012-1230-y","article-title":"Identity-by-descent-based heritability analysis in the Northern Finland Birth Cohort","volume":"132","author":"Browning","year":"2013","journal-title":"Hum. Genet."},{"key":"2023012710454040700_btt734-B6","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1101\/gr.083634.108","article-title":"Fast and flexible simulation of DNA sequence data","volume":"19","author":"Chen","year":"2009","journal-title":"Genome Res."},{"key":"2023012710454040700_btt734-B7","doi-asserted-by":"crossref","first-page":"1264","DOI":"10.1056\/NEJMoa054013","article-title":"Sequence variations in PCSK9, low LDL, and protection against coronary heart disease","volume":"354","author":"Cohen","year":"2006","journal-title":"N. Engl. J. Med."},{"key":"2023012710454040700_btt734-B8","doi-asserted-by":"crossref","first-page":"904","DOI":"10.1016\/j.ajhg.2013.04.025","article-title":"Genome-wide characterization of shared and distinct genetic components that influence blood lipid levels in ethnically diverse human populations","volume":"92","author":"Coram","year":"2013","journal-title":"Am. J. Hum. Genet."},{"key":"2023012710454040700_btt734-B9","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1038\/nrg2809","article-title":"Missing heritability and strategies for finding the underlying causes of complex disease","volume":"11","author":"Eichler","year":"2010","journal-title":"Nat. Rev. Genet."},{"key":"2023012710454040700_btt734-B10","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1038\/mp.2008.100","article-title":"Population-based linkage analysis of schizophrenia and bipolar case-control cohorts identifies a potential susceptibility locus on 19q13","volume":"15","author":"Francks","year":"2010","journal-title":"Mol. Psychiatry"},{"key":"2023012710454040700_btt734-B11","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":"2023012710454040700_btt734-B12","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM"},{"key":"2023012710454040700_btt734-B13","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1101\/gr.081398.108","article-title":"Whole population, genome-wide mapping of hidden relatedness","volume":"19","author":"Gusev","year":"2009","journal-title":"Genome Res."},{"key":"2023012710454040700_btt734-B14","doi-asserted-by":"crossref","first-page":"706","DOI":"10.1016\/j.ajhg.2011.04.023","article-title":"DASH: a method for identical-by-descent haplotype mapping uncovers association with recent variation","volume":"88","author":"Gusev","year":"2011","journal-title":"Am. J. Hum. Genet."},{"key":"2023012710454040700_btt734-B15","doi-asserted-by":"crossref","first-page":"i162","DOI":"10.1093\/bioinformatics\/btt237","article-title":"IBD-Groupon: an efficient method for detecting group-wise identity-by-descent regions simultaneously in multiple individuals based on pairwise IBD relationships","volume":"29","author":"He","year":"2013","journal-title":"Bioinformatics"},{"key":"2023012710454040700_btt734-B16","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1093\/bioinformatics\/btq078","article-title":"SPICi: a fast clustering algorithm for large biological networks","volume":"26","author":"Jiang","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012710454040700_btt734-B17","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1038\/ng.75","article-title":"Six new loci associated with blood low-density lipoprotein cholesterol, high-density lipoprotein cholesterol or triglycerides in humans","volume":"40","author":"Kathiresan","year":"2008","journal-title":"Nat. Genet."},{"key":"2023012710454040700_btt734-B18","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1038\/nbt1096","article-title":"Systematic interpretation of genetic interactions using protein networks","volume":"23","author":"Kelley","year":"2005","journal-title":"Nat. Biotechnol."},{"key":"2023012710454040700_btt734-B19","doi-asserted-by":"crossref","first-page":"e1002496","DOI":"10.1371\/journal.pgen.1002496","article-title":"The empirical power of rare variant association methods: results from sanger sequencing in 1998 individuals","volume":"8","author":"Ladouceur","year":"2012","journal-title":"PLoS Genet."},{"key":"2023012710454040700_btt734-B20","doi-asserted-by":"crossref","first-page":"e1000481","DOI":"10.1371\/journal.pgen.1000481","article-title":"Discovery of rare variants via sequencing: implications for the design of complex trait association studies","volume":"5","author":"Li","year":"2009","journal-title":"PLoS Genet."},{"key":"2023012710454040700_btt734-B21","doi-asserted-by":"crossref","first-page":"e56379","DOI":"10.1371\/journal.pone.0056379","article-title":"Identity-by-descent mapping to detect rare variants conferring susceptibility to multiple sclerosis","volume":"8","author":"Lin","year":"2013","journal-title":"PLoS One"},{"key":"2023012710454040700_btt734-B22","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1093\/biomet\/84.2.309","article-title":"Variance component testing in generalised linear models with random effects","volume":"84","author":"Lin","year":"1997","journal-title":"Biometrika"},{"key":"2023012710454040700_btt734-B23","doi-asserted-by":"crossref","first-page":"e1000384","DOI":"10.1371\/journal.pgen.1000384","article-title":"A groupwise association test for rare mutations using a weighted sum statistic","volume":"5","author":"Madsen","year":"2009","journal-title":"PLoS Genet."},{"key":"2023012710454040700_btt734-B24","doi-asserted-by":"crossref","first-page":"1387","DOI":"10.1098\/rstb.2005.1673","article-title":"Approximating the coalescent with recombination","volume":"360","author":"McVean","year":"2005","journal-title":"Philos. Trans. R. Soc. Lond. B Biol. Sci."},{"key":"2023012710454040700_btt734-B25","doi-asserted-by":"crossref","first-page":"1168","DOI":"10.1101\/gr.115360.110","article-title":"A method for detecting IBD regions simultaneously in multiple individuals\u2013with applications to disease genetics","volume":"21","author":"Moltke","year":"2011","journal-title":"Genome Res."},{"key":"2023012710454040700_btt734-B26","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":"2023012710454040700_btt734-B27","doi-asserted-by":"crossref","first-page":"e1001555","DOI":"10.1371\/journal.pbio.1001555","article-title":"The geography of recent genetic ancestry across Europe","volume":"11","author":"Ralph","year":"2013","journal-title":"PLoS Biol."},{"key":"2023012710454040700_btt734-B28","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1038\/ng.271","article-title":"Genomewide association analysis of metabolic traits in a birth cohort from a founder population","volume":"41","author":"Sabatti","year":"2009","journal-title":"Nat. Genet."},{"key":"2023012710454040700_btt734-B29","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1016\/j.gde.2009.04.010","article-title":"Common vs. rare allele hypotheses for complex diseases","volume":"19","author":"Schork","year":"2009","journal-title":"Curr. Opin. Genet. Dev."},{"key":"2023012710454040700_btt734-B30","doi-asserted-by":"crossref","first-page":"3143","DOI":"10.1093\/bioinformatics\/btp551","article-title":"How and when should interactome-derived clusters be used to predict functional modules and protein function?","volume":"25","author":"Song","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012710454040700_btt734-B31","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1038\/nature09270","article-title":"Biological, clinical and population relevance of 95 loci for blood lipids","volume":"466","author":"Teslovich","year":"2010","journal-title":"Nature"},{"key":"2023012710454040700_btt734-B32","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.ajhg.2011.05.029","article-title":"Rare-variant association testing for sequencing data with the sequence kernel association test","volume":"89","author":"Wu","year":"2011","journal-title":"Am. J. Hum. Genet."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/7\/915\/48921782\/bioinformatics_30_7_915.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/7\/915\/48921782\/bioinformatics_30_7_915.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T11:19:08Z","timestamp":1674818348000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/7\/915\/235086"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,19]]},"references-count":32,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2014,4,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt734","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,4,1]]},"published":{"date-parts":[[2013,12,19]]}}}