title: Efficient clustering of identity-by-descent between multiple individuals.
abstract: BACKGROUND
  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.
  
  
  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.
  
  
  METHODS
  Source code is available under the GNU Public License http://cs.au.dk/~qianyuxx/EMI/.
authors.affiliation: Bioinformatics Research Center, Aarhus Universitet, 8000C Aarhus, Denmark, Department of Biostatistics and Division of Medical Genetics, Department of Medicine, University of Washington, Seattle, WA, USA.
authors.forename: Yu
authors.initials: Y
authors.lastname: Qian
authors.forename: Brian L
authors.initials: BL
authors.lastname: Browning
authors.forename: Sharon R
authors.initials: SR
authors.lastname: Browning
mesh_terms: D000465:Algorithms; D008078:Cholesterol, LDL / Q000235:genetics; D016000:Cluster Analysis; D015331:Cohort Studies; D023281:Genomics; D006239:Haplotypes; D006801:Humans; D020641:Polymorphism, Single Nucleotide; D000071449:Proprotein Convertase 9; D043484:Proprotein Convertases / Q000235:genetics; D012697:Serine Endopeptidases / Q000235:genetics
chemical_list: D008078:Cholesterol, LDL; C472125:PCSK9 protein, human; D000071449:Proprotein Convertase 9; D043484:Proprotein Convertases; D012697:Serine Endopeptidases