A graphical algorithm for fast computation of identity coefficients and generalized kinship coefficients.

Area of Science:

• Genetics
• Computational Biology
• Bioinformatics

Background:

• Computing identity by descent (IBD) sharing probabilities for multiple genes is computationally intensive.
• Existing methods often struggle with large pedigrees or a high number of genes (n).

Purpose of the Study:

• To develop an efficient algorithm for computing generalized kinship coefficients for n genes.
• To simplify the computational complexity of IBD probability calculations.

Main Methods:

• A novel graphical algorithm is presented.
• The algorithm transforms pedigree recursion into a single traversal of a kinship graph.
• Implementation details for n=4 are available in the IdCoefs software package.

Main Results:

• The graphical algorithm efficiently computes all generalized kinship coefficients for n genes.
• The method significantly reduces computational challenges compared to traditional recursive approaches.

Conclusions:

• The developed graphical algorithm offers an efficient solution for calculating IBD sharing probabilities.
• This approach enhances the feasibility of genetic analyses involving complex pedigrees and numerous genes.