Paralelização da Geração de Consistência em Alinhamentos Múltiplos de Sequências Genéticas

• Mario João Jr. UERJ / UFF
• Alexandre C. Sena UERJ
• Vinod E. F. Rebello UFF

DOI: https://doi.org/10.5753/eradrj.2024.4571

Resumo

O Alinhamento Múltiplo de Sequências genéticas é uma etapa essencial na resolução de vários problemas da área de bioinformática. Devido à sua complexidade exponencial, heurísticas são utilizadas. A que obtém os melhores resultados, mas possui o maior custo computacional, é o Alinhamento baseado em Consistência. Este trabalho apresenta a paralelização da geração da consistência, fase fundamental para esta heurística de alinhamento múltiplo. Os resultados obtidos mostram o desempenho da paralelização proposta, sendo capaz de reduzir o tempo de execução da consistência significativamente.

Referências

Durbin, R., Eddy, S. R., Krogh, A., and Mitchison, G. (1998). Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge University Press.

Edgar, R. C. and Batzoglou, S. (2006). Multiple sequence alignment. Current Opinion in Structural Biology, 16(3):368–373.

Feng, D.-F. and Doolittle, R. F. (1987). Progressive Sequence Alignment as a Prerequisite to Correct Phylogenetic Trees. Journal of Molecular Evolution, 25:351–360.

Finn, R. D., Bateman, A., Clements, J., Coggill, P., Eberhardt, R. Y., Eddy, S. R., Heger, A., Hetherington, K., Holm, L., Mistry, J., Sonnhammer, E. L., Tate, J., and Punta, M. (2014). Pfam: the protein families database. Nucleic acids research, 42.

Hung, L.-W., Wang, I. X., Nikaido, K., Liu, P.-Q., Ames, G. F.-L., and Kim, S.-H. (1998). Crystal structure of the ATP-binding subunit of an ABC transporter. Nature, 396(6712):703–707.

João Jr, M., Sena, A. C., and Rebello, V. E. F. (2023a). Fragmentando o DNA de Ferramentas de Alinhamento Progressivo: uma Metaferramenta Eficiente. In Anais do XXIV Simpósio em Sistemas Computacionais de Alto Desempenho, pages 349–360. SBC.

João Jr, M., Sena, A. C., and Rebello, V. E. F. (2023b). On closing the inopportune gap with consistency transformation and iterative refinement. PLoS ONE, 18(7):1–24.

Mirarab, S. and Warnow, T. (2011). FastSP: linear time calculation of alignment accuracy. Bioinformatics, 27(23):3250–3258.

Notredame, C., Higgins, D. G., and Heringa, J. (2000). T-Coffee: A Novel Method for Fast and Accurate Multiple Sequence Alignment. Journal of Molecular Biology, 302(1):205 – 217.

Thompson, J. D., Linard, B., Lecompte, O., and Poch, O. (2011). A Comprehensive Benchmark Study of Multiple Sequence Alignment Methods: Current Challenges and Future Perspectives. PLoS ONE, 6(3).

Wang, L. and Jiang, T. (1994). On the complexity of multiple sequence alignment. Journal of Computational Biology, 1(4):337–348.

Zola, J., Yang, X., Rospondek, S., and Aluru, S. (2007). Parallel T-Coffee: A Parallel Multiple Sequence Aligner. ISCA International Conference on Parallel and Distributed Computing and Systems (PDCS), pages 248–253.