Tópicos em Algoritmos e Complexidade de Probelmas em Bioinformática e Strings
Ementa:
Fundamentos biológicos e modelagem computacional de DNA, genes, cromossomos, genomas, RNA e proteínas. Representação de sequências biológicas por strings, orientação e complemento reverso. Formulação de problemas computacionais em bioinformática. Problemas de decisão e de otimização; classes P e NP; NP-completude, certificados e reduções polinomiais, com aplicações a alinhamento de sequências, subsequência comum mais longa, seleção de primers, estrutura de RNA e rearranjos de genomas. Algoritmos parametrizados: classes FPT e XP, kernelização, árvores de busca limitada, largura de árvore, hierarquia W e limites para kernels. Algoritmos de aproximação e reduções que preservam aproximação. Indexação e busca exata em sequências: tries, árvores de sufixos, árvores de sufixos generalizadas, vetores de sufixos, prefix doubling, busca binária e transformação de Burrows-Wheeler. Genômica comparativa: blocos conservados, genomas lineares, circulares e multicromossômicos, adjacências e telômeros, operações SCJ e DCJ, grafo de adjacências, distância e ordenação por DCJ e problemas de consenso genômico.
Bibliografia:
Garey, M. R.; Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
Dasgupta, S.; Papadimitriou, C. H.; Vazirani, U. V. Algorithms. McGraw-Hill, 2008.
Cygan, M.; Fomin, F. V.; Kowalik, Ł.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S. Parameterized Algorithms. Springer, 2015.
Gusfield, D. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
Crochemore, M.; Hancart, C.; Lecroq, T. Algorithms on Strings. Cambridge University Press, 2007.
Fertin, G.; Labarre, A.; Rusu, I.; Tannier, E.; Vialette, S. Combinatorics of Genome Rearrangements. MIT Press, 2009.
Pevzner, P. A. Computational Molecular Biology: An Algorithmic Approach. MIT Press, 2000.
Setubal, J. C.; Meidanis, J. Introduction to Computational Molecular Biology. PWS Publishing Company, 1997.
Stoye, J. et al. Sequence Analysis. Lecture Notes, Faculty of Technology, Bielefeld University, 2024/2025.
Slides:
- Aula 0 - Apresentação do curso
- Aula 1 - Fundamentos biológicos e modelagem computacional
- Aula 2 - Complexidade e reduções em bioinformática
- Aula 3 - Algoritmos parametrizados e aproximação
- Aula 4 - Indexação e busca em sequências
- Aula 5 - Genômica comparativa, rearranjos e DCJ
Se você tem alguma dúvida ou sugestão, sinta-se à vontade em me mandar uma mensagem. email.