Iterative Level-0: A new and fast algorithm to traverse mating networks calculating the inbreeding and relationship...

Area of Science:

• Population Medical Genetics
• Computational Biology
• Bioinformatics

Background:

• Calculating inbreeding and relationship coefficients is vital for studying autosomal recessive disorders in endogamous populations.
• Existing methods struggle with large, complex mating networks due to traversal inefficiencies.
• Depth First Search (DFS) and Breadth First Search (BFS) are common but computationally intensive algorithms for network traversal.

Purpose of the Study:

• To introduce and detail the Iterative Level-0 (IL0) algorithm for efficient mating network traversal.
• To demonstrate the superiority of IL0 over DFS-based and BFS-based algorithms in calculating genetic coefficients.
• To provide a user-friendly Cytoscape application for practical implementation and comparison.

Main Methods:

• Development of the Iterative Level-0 (IL0) algorithm for mating network traversal.
• Implementation of IL0, DFS-based, and BFS-based algorithms within a Cytoscape application.
• Experimental validation using diverse mating networks across different species (humans, primates, dogs) and complexities.

Main Results:

• The IL0 algorithm significantly outperforms DFS and BFS, achieving a speedup of 7.60 to 127.50 times.
• IL0 exhibits linear runtime dependence on the number of edges, while DFS and BFS show quadratic dependence, indicating superior scalability.
• Runtime and scalability studies confirm IL0's efficiency in calculating inbreeding and relationship coefficients for complex networks.

Conclusions:

• The IL0 algorithm offers a substantial computational advantage for analyzing genetic coefficients in large mating networks.
• IL0 provides a more scalable solution compared to traditional DFS and BFS methods, especially for complex biological networks.
• The freely available Cytoscape application facilitates the practical application and comparison of these algorithms in population genetics research.