Análise experimental da complexidade do problema da minimização da consanguinidade em sistemas de acasalamento
Resumo
O melhoramento animal depende de sistemas de acasalamento para produzir a melhor próxima geração do rebanho. Além do ganho genético e econômico esperado, a consanguinidade do rebanho deve ser mantida baixa, para evitar problemas gerados por depressão endogâmica. Este trabalho objetiva iniciar o estudo da complexidade do problema da minimização da consanguinidade usando uma combinação de programação linear com branch-and-bound, para investigar o tempo de execução médio da solução do problema. Os resultados apontam que o problema parece ser computacionalmente intratável.
Referências
Arksey, H. and O’Malley, L. (2005). Scoping studies: Towards a methodological framework. Int. J. Social Research Methodology, 8(1):19–32.
Arora, S. and Barak, B. (2009). Computational Complexity: a Modern Approach. Cambridge University Press, Cambridge, UK.
Bates, D. and Vazquez, A. I. (2015). pedigreemm: Pedigree-based mixed-effects models. R package version 0.3-3.
Berkelaar, M. et al. (2020). Interface to lp solve v. 5.5 to solve linear/integer programs. R package.
Dantzig, G. B. (1963). Linear programming and extensions. Princeton University Press.
Eler, J. P. (2017). Teorias e métodos em melhoramento genético animal: seleção. Faculdade de Zootecnia e Engenharia de Alimentos da USP, Pirassununga – São Paulo.
Fernández, J., Toro, M., and Caballero, A. (2003). Fixed contributions designs vs. minimization of global coancestry to control inbreeding in small populations. Genetics, 165(2):885–894.
Ferreira, A. P. L. (2021). On the problem of compensatory mating in animal breeding. In Anais do VI Workshop-Escola de Informática Teórica (WEIT 2021), pages 96–103, Bagé, RS.
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.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences. W. H. Freeman, 1st edition.
Henryon, M., Sørensen, A., and Berg, P. (2009). Mating animals by minimising the covariance between ancestral contributions generates less inbreeding without compromising genetic gain in breeding schemes with truncation selection. Animal, 3(10):1339–1346.
Hillier, F. S. and Lieberman, G. J. (2013). Introdução à pesquisa operacional. McGraw-Hill Brasil, Porto Alegre.
Honda, T., Nomura, T., and Mukai, F. (2005). Prediction of inbreeding in commercial females maintained by rotational mating with partially isolated sire lines. Journal of Animal Breeding and Genetics, 122(5):340–348.
Lawler, E. L. (1966). Branch and bound methods for integer programming. INFORMS Journal on Computing, 7(1):73–87.
Lenstra, A. and Kan, S. (1983). Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538–548.
Liu, H., Henryon, M., and Sørensen, A. (2017). Mating strategies with genomic information reduce rates of inbreeding in animal breeding schemes without compromising genetic gain. Animal, 11(4):547–555.
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.
Motta, B. E. T. (2021). BrangusSelection: algoritmo de otimização para seleção de acasalamentos de bovinos com foco na maximização dos ganhos financeiros. Master’s thesis, Programa de Pós-graduação em Computação Aplicada, Universidade Federal do Pampa.
Motta, B. E. T., Ferreira, A. P. L., and Yokoo, M. J.-I. (2021). BrangusSelection: um algoritmo para seleção ótima de acasalamentos com índice de seleção customizável. In Anais do XIII Congresso Brasileiro de Agroinformática, pages 35–43, Porto Alegre. Sociedade Brasileira de Computação.
Nomura, T. (1999). A mating system to reduce inbreeding in selection programmes: theoretical basis and modification of compensatory mating. Journal of Animal Breeding and Genetics, 116(5):351–361.
Nomura, T., Yamaguchi, S., Mukai, F., and Yamamoto, A. (2002). Optimization of selection and mating schemes in closed broiler lines. Animal science journal, 73(6):435–443.
Nomura, T. and Yonezawa, K. (1996). A comparison of four systems of group mating for avoiding inbreeding. Genetics Selection Evolution, 28(2):141–159.
Paiva, A. L. C. (2010). Avaliação de métodos de controle de endogamia utilizando dados simulados.
Pryce, J., Hayes, B., and Goddard, M. (2012). Novel strategies to minimize progeny inbreeding while maximizing genetic gain using genomic information. Journal of dairy science, 95(1):377–388.
Sanders, P., Mehlhorn, K., Dietzfelbinger, M., and Dementiev, R. (2019). Generic Approaches to Optimization, pages 357–392. Springer International Publishing, Cham.
Simões, M. R. S., Leal, J. J. B., Minho, A. P., Gomes, C. C., MacNeil, M. D., Costa, R. F., Junqueira, V. S., Schmidt, P. I., Cardoso, F. F., Boligon, A. A., and Yokoo, M. J. (2020). Breeding objectives of Brangus cattle in brazil. Journal of Animal Breeding and Genetics, 137(2):177–188.
Weigeland, K. and Lin, S. (2002). Controlling inbreeding by constraining the average relationship between parents of young bulls entering ai progeny test programs. Journal of dairy science, 85(9):2376–2383.
Arora, S. and Barak, B. (2009). Computational Complexity: a Modern Approach. Cambridge University Press, Cambridge, UK.
Bates, D. and Vazquez, A. I. (2015). pedigreemm: Pedigree-based mixed-effects models. R package version 0.3-3.
Berkelaar, M. et al. (2020). Interface to lp solve v. 5.5 to solve linear/integer programs. R package.
Dantzig, G. B. (1963). Linear programming and extensions. Princeton University Press.
Eler, J. P. (2017). Teorias e métodos em melhoramento genético animal: seleção. Faculdade de Zootecnia e Engenharia de Alimentos da USP, Pirassununga – São Paulo.
Fernández, J., Toro, M., and Caballero, A. (2003). Fixed contributions designs vs. minimization of global coancestry to control inbreeding in small populations. Genetics, 165(2):885–894.
Ferreira, A. P. L. (2021). On the problem of compensatory mating in animal breeding. In Anais do VI Workshop-Escola de Informática Teórica (WEIT 2021), pages 96–103, Bagé, RS.
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.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences. W. H. Freeman, 1st edition.
Henryon, M., Sørensen, A., and Berg, P. (2009). Mating animals by minimising the covariance between ancestral contributions generates less inbreeding without compromising genetic gain in breeding schemes with truncation selection. Animal, 3(10):1339–1346.
Hillier, F. S. and Lieberman, G. J. (2013). Introdução à pesquisa operacional. McGraw-Hill Brasil, Porto Alegre.
Honda, T., Nomura, T., and Mukai, F. (2005). Prediction of inbreeding in commercial females maintained by rotational mating with partially isolated sire lines. Journal of Animal Breeding and Genetics, 122(5):340–348.
Lawler, E. L. (1966). Branch and bound methods for integer programming. INFORMS Journal on Computing, 7(1):73–87.
Lenstra, A. and Kan, S. (1983). Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538–548.
Liu, H., Henryon, M., and Sørensen, A. (2017). Mating strategies with genomic information reduce rates of inbreeding in animal breeding schemes without compromising genetic gain. Animal, 11(4):547–555.
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.
Motta, B. E. T. (2021). BrangusSelection: algoritmo de otimização para seleção de acasalamentos de bovinos com foco na maximização dos ganhos financeiros. Master’s thesis, Programa de Pós-graduação em Computação Aplicada, Universidade Federal do Pampa.
Motta, B. E. T., Ferreira, A. P. L., and Yokoo, M. J.-I. (2021). BrangusSelection: um algoritmo para seleção ótima de acasalamentos com índice de seleção customizável. In Anais do XIII Congresso Brasileiro de Agroinformática, pages 35–43, Porto Alegre. Sociedade Brasileira de Computação.
Nomura, T. (1999). A mating system to reduce inbreeding in selection programmes: theoretical basis and modification of compensatory mating. Journal of Animal Breeding and Genetics, 116(5):351–361.
Nomura, T., Yamaguchi, S., Mukai, F., and Yamamoto, A. (2002). Optimization of selection and mating schemes in closed broiler lines. Animal science journal, 73(6):435–443.
Nomura, T. and Yonezawa, K. (1996). A comparison of four systems of group mating for avoiding inbreeding. Genetics Selection Evolution, 28(2):141–159.
Paiva, A. L. C. (2010). Avaliação de métodos de controle de endogamia utilizando dados simulados.
Pryce, J., Hayes, B., and Goddard, M. (2012). Novel strategies to minimize progeny inbreeding while maximizing genetic gain using genomic information. Journal of dairy science, 95(1):377–388.
Sanders, P., Mehlhorn, K., Dietzfelbinger, M., and Dementiev, R. (2019). Generic Approaches to Optimization, pages 357–392. Springer International Publishing, Cham.
Simões, M. R. S., Leal, J. J. B., Minho, A. P., Gomes, C. C., MacNeil, M. D., Costa, R. F., Junqueira, V. S., Schmidt, P. I., Cardoso, F. F., Boligon, A. A., and Yokoo, M. J. (2020). Breeding objectives of Brangus cattle in brazil. Journal of Animal Breeding and Genetics, 137(2):177–188.
Weigeland, K. and Lin, S. (2002). Controlling inbreeding by constraining the average relationship between parents of young bulls entering ai progeny test programs. Journal of dairy science, 85(9):2376–2383.
Publicado
08/11/2023
Como Citar
ROSSO, Éric Dias da Silva; FERREIRA, Ana Paula Lüdtke.
Análise experimental da complexidade do problema da minimização da consanguinidade em sistemas de acasalamento. In: CONGRESSO BRASILEIRO DE AGROINFORMÁTICA (SBIAGRO), 14. , 2023, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 32-39.
ISSN 2177-9724.
DOI: https://doi.org/10.5753/sbiagro.2023.26538.
