Solução Exata para Alinhamento Múltiplo de Sequências com Google OR-Tools

Implementação de um modelo de otimização exato para resolver o Problema de Alinhamento Múltiplo de Sequências (MSA). O projeto utiliza Programação Inteira e a biblioteca Google OR-Tools para encontrar o alinhamento ótimo com base na métrica de pontuação de Soma de Pares (Sum-of-Pairs).

Este código é o artefato de implementação do artigo acadêmico: "Aplicação de Técnicas de Pesquisa Operacional ao Problema de Alinhamento Múltiplo de Sequências".

Sobre o Problema

O Alinhamento Múltiplo de Sequências (MSA) visa alinhar três ou mais sequências biológicas (DNA, RNA ou proteína) para identificar regiões conservadas que possam indicar relações funcionais, estruturais ou evolutivas.

Formalmente, o MSA é um problema NP-Completo. Isso significa que o tempo necessário para encontrar a solução ótima cresce exponencialmente com o número e o comprimento das sequências, tornando os métodos exatos inviáveis para instâncias de grande porte. Por essa razão, a maioria das ferramentas populares utiliza heurísticas, que são mais rápidas, mas não garantem a otimalidade da solução.

Este projeto explora os limites de uma abordagem exata em instâncias de pequena escala, fornecendo uma base de referência ("padrão-ouro") para avaliar a qualidade de métodos heurísticos.

O Modelo de Otimização

O problema é formulado como um modelo de Programação Inteira, implementado em Python com a biblioteca Google OR-Tools. O solver utilizado é o CBC (COIN-OR Branch and Cut).

1. Objetivo

Maximizar a pontuação total do alinhamento, calculada pelo método de Soma de Pares (Sum-of-Pairs, SP). A pontuação considera bônus para caracteres idênticos (matches) e penalidades para caracteres distintos (mismatches) e para a inserção de espaços (gaps).

Os parâmetros de pontuação utilizados no modelo são:

• Match: +2
• Mismatch: -1
• Gap: -3

2. Variáveis de Decisão

• $x_{s,i,j}$: Variável binária que é 1 se o caractere i da sequência s é posicionado na coluna j do alinhamento.
• $g_{s,j}$: Variável binária que é 1 se a sequência s possui um gap na coluna j.
• Variáveis auxiliares de linearização para computar as pontuações de pares caractere-caractere ($z^{cc}$) e caractere-gap ($z^{cg}$).

3. Restrições

O modelo garante um alinhamento válido por meio das seguintes restrições principais:

• Atribuição de Caracteres: Cada caractere de cada sequência deve ser posicionado exatamente uma vez no alinhamento.
• Exclusividade da Coluna: Cada coluna do alinhamento pode conter no máximo um caractere de cada sequência.
• Preservação da Ordem: A ordem original dos caracteres dentro de cada sequência deve ser mantida.
• Definição de Gap: Uma posição contém um gap se, e somente se, nenhum caractere da sequência correspondente for alocado naquela coluna.

Tecnologias Utilizadas

• Linguagem: Python 3
• Biblioteca de Otimização: Google OR-Tools

Instalação e Uso

1. Clone o repositório:

   git clone https://github.com/vncsmnl/msa_ortools.git
   cd msa_ortools

2. Instale as dependências: O projeto requer a biblioteca ortools. Instale-a usando pip:

   pip install ortools

3. Execute o script:

   python main.py

   O script solicitará interativamente o número de sequências e o comprimento da primeira sequência. Em seguida, ele irá gerar as sequências aleatoriamente, montar e resolver o modelo de otimização, e exibir o alinhamento ótimo e a pontuação final.

Resultados e Análise

Os resultados práticos confirmam a complexidade teórica do MSA:

• Instâncias de Pequena Escala: Para problemas menores (ex: 3 sequências com até 15 caracteres), o solver encontra e prova a otimalidade da solução em poucos segundos.
• Crescimento Exponencial: Ao aumentar o tamanho das instâncias (ex: 4 sequências com 20 caracteres), o tempo de execução cresce drasticamente, podendo levar várias horas.
• Garantia de Otimalidade: Para todas as instâncias em que o solver converge, a solução obtida é garantidamente ótima segundo a métrica SP, servindo como uma referência fundamental para a avaliação de novos métodos aproximativos.

License

            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
                    Version 2, December 2004

 Copyright (C) 2004 Sam Hocevar <sam@hocevar.net>

 Everyone is permitted to copy and distribute verbatim or modified
 copies of this license document, and changing it is allowed as long
 as the name is changed.

            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

  0. You just DO WHAT THE FUCK YOU WANT TO.

Referências

1. Thompson, J.D., Higgins, D.G., & Gibson, T.J. (1994). CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Research, 22(22), 4673-4680.

2. Katoh, K., & Standley, D.M. (2013). MAFFT multiple sequence alignment software version 7: improvements in performance and usability. Molecular Biology and Evolution, 30(4), 772-780.

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

4. Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press.

5. Needleman, S.B., & Wunsch, C.D. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3), 443-453.

6. Sankoff, D. (1972). Minimal mutation trees of sequences. SIAM Journal on Applied Mathematics, 24(1), 68-76.

7. Durbin, R., Eddy, S.R., Krogh, A., & Mitchison, G. (1998). Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press.

8. Altschul, S.F., Gish, W., Miller, W., Myers, E.W., & Lipman, D.J. (1990). Basic local alignment search tool. Journal of Molecular Biology, 215(3), 403-410.

9. Nemhauser, G.L., & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience.

10. Papadimitriou, C.H. (1994). Computational Complexity. Addison-Wesley.

11. Notredame, C. (2007). Recent evolutions of multiple sequence alignment algorithms. PLoS Computational Biology, 3(8), e123.

12. Edgar, R.C. (2004). MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Research, 32(5), 1792-1797.

13. Korte, B., Vygen, J. (2012). Combinatorial Optimization: Theory and Algorithms. Springer.

14. Wolsey, L.A. (1998). Integer Programming. Wiley.

15. Bertsimas, D., & Tsitsiklis, J. (1997). Introduction to Linear Optimization. Athena Scientific.

16. Google OR-Tools: Open Source Software for Optimization. (2020). Disponível em: https://developers.google.com/optimization

17. Ribeiro, C.C., & Urrutia, S. (2001). A hybrid genetic algorithm for multiple sequence alignment. Computers & Operations Research, 28(12), 1291-1307.

18. Gusfield, D., & Waterman, M.S. (1989). Algorithms for Molecular Biology. Cambridge University Press.

19. Waterman, M.S. (1995). Introduction to Computational Biology: Maps, Sequences and Genomes. Chapman & Hall.

20. Aluru, S. (2005). Handbook of Computational Molecular Biology. Chapman & Hall/CRC.

21. Durbin, R. (1999). Biological Sequence Analysis. Cambridge University Press.

22. Wang, L., & Jiang, T. (1994). On the complexity of multiple sequence alignment. Journal of Computational Biology, 1(4), 337-348.

23. Lee, C., Grasso, C., & Sharlow, M.F. (2002). Multiple sequence alignment using partial order graphs. Bioinformatics, 18(3), 452-464.

24. Blanchette, M., et al. (2004). Aligning multiple genomic sequences with the threaded blockset aligner. Genome Research, 14(4), 708-715.

25. Gotoh, O. (1982). An improved algorithm for matching biological sequences. Journal of Molecular Biology, 162(3), 705-708.

26. Eddy, S.R. (1996). Hidden Markov models. Current Opinion in Structural Biology, 6(3), 361-365.

27. Chatzou, M., Magis, C., Chang, J.M., & Clausen, S. (2016). Multiple sequence alignment modeling: a critical review and recommendations. Briefings in Bioinformatics, 17(6), 975-988.

28. Zhang, Z., & Grosse, I. (2010). Advances in multiple sequence alignment algorithms. Current Bioinformatics, 5(2), 121-130.

29. Notredame, C. (2002). Recent progresses in multiple sequence alignment: a survey. Pharmacogenomics, 3(1), 131-144.

30. Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences. Cambridge University Press.

31. Waterman, M.S., & Eggert, M. (1987). A new algorithm for best subsequence alignments with application to tRNA-rRNA comparisons. Journal of Molecular Biology, 197(3), 723-728.

32. Sankoff, D., & Kruskal, J.B. (1999). Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. CSLI Publications.

33. Alves, R., & Costa, F.F. (2019). Challenges in computational biology: A perspective on optimization problems. Computational and Structural Biotechnology Journal, 17, 1123-1131.

34. Schulz, M.H., et al. (2012). Oases: robust de novo RNA-seq assembly across the dynamic range of expression levels. Bioinformatics, 28(8), 1086-1092.

35. Notredame, C. (2007). Recent evolutions of multiple sequence alignment algorithms. PLoS Computational Biology, 3(8), e123.