Menor-Flores Manuel, Vega-Rodríguez Miguel A, Molina Felipe
Escuela Politécnica, Universidad de Extremadura(1), Campus Universitario s/n, 10003 Cáceres, Spain.
Facultad de Ciencias, Universidad de Extremadura (1), Avda. de Elvas s/n, 06006 Badajoz, Spain.
Comput Biol Med. 2023 Sep;164:107296. doi: 10.1016/j.compbiomed.2023.107296. Epub 2023 Aug 2.
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.
在群体医学遗传学中，对高度近亲通婚群体中的常染色体隐性疾病的研究是一个重要课题，其中在交配网络上计算近亲繁殖系数和亲属关系系数至关重要。然而，在处理大型复杂的交配网络时会出现一个挑战，即在计算过程中难以遍历这些网络。针对此计算，我们提出使用迭代零级（IL0）作为一种新的、更快的算法，它能更高效地遍历交配网络。这项工作的目的是详细解释IL0算法，并通过将其与基于该领域最著名算法的两种算法：深度优先搜索（DFS）和广度优先搜索（BFS）进行比较，来证明其优越性。已开发出一个Cytoscape应用程序，用于计算构成任何交配网络的个体的近亲繁殖系数和亲属关系系数。在这个应用程序中，实现了IL0方案以及基于DFS和BFS的算法。任何用户都可以访问这个免费的Cytoscape应用程序（https://apps.cytoscape.org/apps/inbreeding），它允许对IL0方案与最著名的算法（基于DFS和BFS）进行比较。此外，为了进行实验，还收集了一组在复杂度（边的数量）和物种（人类、灵长类动物和狗）方面各不相同的交配网络。在计算近亲繁殖系数和亲属关系系数时，IL0、基于DFS和基于BFS的算法所获得的运行时间证明了IL0的改进。事实上，一项加速研究表明，IL0算法比基于DFS和基于BFS的算法快7.60至127.50倍。此外，一项可扩展性研究发现，IL0运行时间的增长与交配网络边的数量呈线性相关，而基于DFS和基于BFS的运行时间呈二次相关。因此，IL0算法在计算近亲繁殖系数和亲属关系系数时，比基于著名的DFS和BFS的两种算法快很多倍（高达127.50倍）。此外，我们的结果表明，随着交配网络复杂度增加，IL0的扩展性要好得多。
