A graphical algorithm for fast computation of identity coefficients and generalized kinship coefficients.
Computing the probability of identity by descent sharing among n genes given only the pedigree of those genes is a computationally challenging problem, if n or the pedigree size is large. Here, I present a novel graphical algorithm for efficiently computing all generalized kinship coefficients for n genes. The graphical description transforms the problem from doing many recursion on the pedigree to doing a single traversal of a structure referred to as the kinship graph.


BACKGROUND
The algorithm is implemented for n = 4 in the software package IdCoefs at http://home.uchicago.edu/abney/Software.html.


BACKGROUND
abney@bsd.uchicago.edu


BACKGROUND
Supplementary data are available at Bioinformatics online.
Department of Human Genetics, University of Chicago, Chicago, IL 60637, USA. abney@bsd.uchicago.edu
Mark
M
Abney
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003196:Computer Graphics; D010375:Pedigree; D012984:Software