Dynamic strategy for determining the degree of coancestry in a graph database

• Eric Dias da Silva Rosso Federal University of Pampa (UNIPAMPA)
• Anderson dos Santos da Rosa Federal University of Pampa (UNIPAMPA)
• Ana Paula Lüdtke Ferreira Federal University of Pampa (UNIPAMPA) https://orcid.org/0000-0001-7057-9095

DOI: https://doi.org/10.5753/weit.2023.26593

Abstract

Animal breeding systems control the kinship relationships between the animals in a herd, to prevent the problems arising from inbreeding depression. This paper presents an algorithm for calculating coancestry indexes between animals, implemented on a graph database, and using a dynamic programming strategy. The algorithm does not require to recalculate any values when new animals are inserted into the database. The algorithm is O(n²), which is the minimum expected complexity of an algorithm that computes a full binary relation.

Keywords: Animal breeding, Dynamic Programming, Mating Systems

References

Aguilar, I. and Misztal, I. (2008). Recursive algorithm for inbreeding coefficients assuming nonzero inbreeding of unknown parents. Journal of Dairy science, 91(4):1669-1672. https://doi.org/10.3168/jds.2007-0575

Arksey, H. and O’Malley, L. (2005). Scoping studies: Towards a methodological framework. Int. J. Social Research Methodology, 8(1):19–32. https://doi.org/10.1080/1364557032000119616

Backus, V. and Gilpin, M. (2002). An efficient algorithm for the additive kinship matrix. Journal of Heredity, 93(6):453–456. https://doi.org/10.1093/jhered/93.6.453

Boyce, A. (1983). Computation of inbreeding and kinship coefficients on extended pedigrees. Journal of Heredity, 74(6):400–404. https://doi.org/10.1093/oxfordjournals.jhered.a109825

Cardoso, F. F. (2009). Ferramentas e estratégias para o melhoramento genético de bovinos de corte. Technical report, Embrapa Pecuária Sul, Bagé.

Charlesworth, D. and Willis, J. H. (2009). The genetics of inbreeding depression. Nature Reviews Genetics, 10:783-796. https://doi.org/10.1038/nrg2664

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2002). Algoritmos: teoria e prática. Editora Campus, 2nd edition.

Diestel, R. (2005). Graph Theory. Graduate Texts in Mathematics. Springer.

Elliott, B. et al. (2009). Efficiently calculating inbreeding on large pedigrees databases. Information systems, 34(6):469-492. https://doi.org/10.1016/j.is.2009.02.002

Falconer, D. S. and Mackay, T. F. C. (1996). Introduction to Quantitative Genetics. Longman Group Ltd., Harlow, 4th edition.

Ferreira, A. P. L., Yokoo, M. J.-I., and Motta, B. E. T. (2021). On the problem of optimal mating in animal breeding. In Simposio Latinoamericano de Teoría Computacional, Proceedings of the XLVII Conferencia Latinoamericana de Informática (CLEI 2021), pages 1-7, San José, Costa Rica. IEEE. https://doi.org/10.1109/CLEI53233.2021.9640023.

Gholami, K. and Thomas, A. (1994). A linear time algorithm for calculation of multiple pairwise kinship coefficients and the genetic index of familiality. Computers and Biomedical Research, 27(5):342-350. https://doi.org/10.1006/cbmr.1994.1026

Heckel, R., Corradini, A., Ehrig, H., and Löwe, M. (1996). Horizontal and vertical structuring of typed graph transformation systems. Mathematical Structures in Computer Science, 6(6):613–648. https://doi.org/10.1017/S0960129500070110

Khang, J. V. T. (1989). A FORTRAN subroutine to compute inbreeding and kinship coefficients according to the number of ancestral generations. Bioinformatics, 5(3):199–204. https://doi.org/10.1093/bioinformatics/5.3.199

Mi, M. P., Chapman, A. R., and Tyler,W. J. (1965). Effect of mating system on production traits in dairy cattle. J. Dairy Sci., 48:77–84. https://doi.org/10.3168/jds.S0022-0302(65)88164-4

Robinson, I., Webber, J., and Eifrem, E. (2015). Graph databases: new opportunities for connected data. O’Reilly Media, Inc.

Toscani, L. V. and Veloso, P. A. S. (2006). Complexidade de Algoritmos: análise, projeto e métodos. Bookman, Porto Alegre, 2nd edition.