Estratégia dinâmica para determinação de grau de coancestralidade em um banco de dados orientado a grafos
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.
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
Como Citar
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.
