Efficient path-based computations on pedigree graphs with compact encodings.

Area of Science:

• Genetics
• Bioinformatics
• Computational Biology

Background:

• Pedigree analysis is crucial for understanding genetic disease inheritance patterns.
• Efficient computation of genealogical measurements like inbreeding coefficients is vital for large datasets.
• Existing path-based methods face scalability challenges with extensive pedigree data.

Purpose of the Study:

• To propose a novel, compact path encoding scheme for large pedigrees.
• To develop an efficient algorithm for path identification within these pedigrees.
• To enhance the computation of inbreeding coefficients using the new method.

Main Methods:

• Developed a compact path encoding scheme for large pedigree graphs.
• Designed an efficient algorithm for identifying paths in encoded pedigrees.
• Applied the method to compute inbreeding coefficients, comparing performance against existing techniques.

Main Results:

• The proposed method demonstrates superior time and space efficiency compared to previous approaches.
• Experimental results on real and synthetic pedigree data validate the method's scalability.
• Theoretical complexity analysis supports the efficiency gains.

Conclusions:

• The new path encoding and identification method offers a more scalable and efficient solution for analyzing large pedigrees.
• This advancement facilitates more effective computation of genealogical measurements, aiding genetic research.
• The method provides a significant improvement for inbreeding coefficient calculation in large-scale genetic studies.