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

In population medical genetics, the study of autosomal recessive disorders in highly endogamous populations is a major topic where calculating the inbreeding and relationship coefficients on mating networks is crucial. However, a challenge arises when dealing with large and complex mating networks, making their traversal difficult during the calculation process. For this calculation, we propose using Iterative Level-0 (IL0) as a new and faster algorithm that traverses mating networks more efficiently. The purpose of this work is to explain in detail the IL0 algorithm and prove its superiority by comparing it with two algorithms based on the best-known algorithms in the area: Depth First Search (DFS) and Breadth First Search (BFS). A Cytoscape application has been developed to calculate the inbreeding and relationship coefficients of individuals composing any mating network. In this application, the IL0 proposal together with DFS-based and BFS-based algorithms have been implemented. Any user can access this freely available Cytoscape application (https://apps.cytoscape.org/apps/inbreeding) that allows the comparison between the IL0 proposal and the best-known algorithms (based on DFS and BFS). In addition, a diverse set of mating networks has been collected in terms of complexity (number of edges) and species (humans, primates, and dogs) for the experiments. The runtime obtained by the IL0, DFS-based, and BFS-based algorithms when calculating the inbreeding and relationship coefficients proved the improvement of IL0. In fact, a speedup study reflected that the IL0 algorithm is 7.60 to 127.50 times faster than DFS-based and BFS-based algorithms. Moreover, a scalability study found that the growth of the IL0 runtime has a linear dependence on the number of edges of the mating network, while the DFS-based and BFS-based runtimes have a quadratic dependence. Therefore, the IL0 algorithm can solve the problem of calculating the inbreeding and relationship coefficients many times faster (up to 127.50) than the two algorithms based on the famous DFS and BFS. Furthermore, our results demonstrate that IL0 scales much better as the complexity of mating networks increases.