Estratégia dinâmica para determinação de grau de coancestralidade em um banco de dados orientado a grafos

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

Resumo


Sistemas de melhoramento animal controlam as relações de parentesco do rebanho para evitar os problemas decorrentes de depressão por consanguinidade. Este trabalho apresenta um algoritmo para cálculo da coancestralidade entre animais, implementado sobre um banco de dados de grafos e usando uma estratégia de programação dinâmica. O algoritmo tem complexidade quadrática, que é a complexidade mínima esperada de um algoritmo que computa uma relação binária total.

Palavras-chave: Melhoramento animal, Programação Dinâmica, Sistemas de Acasalamento

Referências

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.
Publicado
09/10/2023
ROSSO, Eric Dias da Silva; ROSA, Anderson dos Santos da; FERREIRA, Ana Paula Lüdtke. Estratégia dinâmica para determinação de grau de coancestralidade em um banco de dados orientado a grafos. In: WORKSHOP-ESCOLA DE INFORMÁTICA TEÓRICA (WEIT), 7. , 2023, Rio Grande/RS. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 19-28. DOI: https://doi.org/10.5753/weit.2023.26593.