An Efficient Algorithm for the Additive Kinship Matrix
V. Backus, M. Gilpin · Journal of Heredity · 2002
In this article we show how object-oriented programming can provide an efficient method for calculating kinship coefficients for very large pedigrees—large in number of individuals or generations, or both. We call our approach the “compressed kinship matrix.” We use Java as our object-oriented language, but the algorithm should be similarly implemented in other object-oriented languages. The documented source code and illustrative Java applets are available on our Web site: www.consbio.com/kinshipAlgorithm. Specification of the genealogical relationships between all individuals in a population is the most complete and fundamental nonempirical genetic analysis one can perform (Lacy et al. 1995). Kinship, the probability that two individuals share alleles identical by descent, plays a central role in the study of these relationships (Thompson 1976). Although first utilized for human pedigrees, it is also important for the genetic management of animals in captive or domesticated settings for which exact paternity information is available. The kinship between two individuals is equal to the inbreeding coefficient an offspring of theirs would have regardless of whether the two individuals have actually mated. Boyce (1983) reviews the two main computation approaches for calculating inbreeding and kinship coefficients: path analysis and recursive algorithms. Path analysis algorithms lend themselves to computational problems on extended pedigrees owing to the large number of paths that need to be generated, stored, and searched. For pedigrees of substantial depth, programming of the recursive algorithm is more straightforward.