title: Efficient identification of equivalences in dynamic graphs and pedigree structures.
abstract: We propose a new framework for designing test and query functions for complex structures that vary across a given parameter such as genetic marker position. The operations we are interested in include equality testing, set operations, isolating unique states, duplication counting, or finding equivalence classes under identifiability constraints. A motivating application is locating equivalence classes in identity-by-descent (IBD) graphs, which are graph structures in pedigree analysis that change over genetic marker location. The nodes of these graphs are unlabeled and identified only by their connecting edges, a constraint easily handled by our approach. The general framework introduced is powerful enough to build a range of testing functions for IBD graphs, dynamic populations, and other structures using a minimal set of operations. The theoretical and algorithmic properties of our approach are analyzed and proved. Computational results on several simulations demonstrate the effectiveness of our approach.
authors.affiliation: University of Washington, Department of Statistics, Washington 98195, USA. hoytak@u.washington.edu
authors.forename: Hoyt
authors.initials: H
authors.lastname: Koepke
authors.forename: Elizabeth
authors.initials: E
authors.lastname: Thompson
mesh_terms: D000465:Algorithms; D003196:Computer Graphics; D003198:Computer Simulation; D005260:Female; D005819:Genetic Markers; D006801:Humans; D008297:Male; D010375:Pedigree; D040641:Quantitative Trait Loci / Q000235:genetics*
chemical_list: D005819:Genetic Markers
references.citation: Proc Natl Acad Sci U S A. 1984 Jun;81(11):3443-6
references.pmid: 6587361
references.citation: Genet Epidemiol. 2012 Sep;36(6):602-11
references.pmid: 22740194
references.citation: Proc Natl Acad Sci U S A. 1987 Apr;84(8):2363-7
references.pmid: 3470801
references.citation: Hum Hered. 1971;21(6):523-42
references.pmid: 5149961
references.citation: Hum Hered. 2011;71(2):86-96
references.pmid: 21734399
references.citation: Am J Hum Genet. 1996 Jun;58(6):1323-37
references.pmid: 8651310
references.citation: Stat Appl Genet Mol Biol. 2012 Jan 06;11(2):
references.pmid: 22499699
references.citation: Genetics. 2012 Apr;190(4):1447-60
references.pmid: 22298700
references.citation: Am J Hum Genet. 1996 Jun;58(6):1347-63
references.pmid: 8651312
references.citation: Hum Hered. 2008;65(3):142-53
references.pmid: 17934317
references.citation: Philos Trans R Soc Lond B Biol Sci. 1994 Jun 29;344(1310):345-50; discussion 350-1
references.pmid: 7800704
references.citation: Am J Hum Genet. 2010 Apr 9;86(4):526-39
references.pmid: 20303063
references.citation: Am J Hum Genet. 1991 Dec;49(6):1320-34
references.pmid: 1746559
references.citation: Hum Hered. 2011;72(4):289-97
references.pmid: 22189471