Introdução

As recentes pesquisas sobre os genomas de diversas formas de vida suscitaram diversos problemas computacionais. Devido ao grande tamanho dos genomas, mapeá-los torna-se uma tarefa difícil em que o uso de programas de computador preparados para a comparação de seqüências e para o casamento de padrões em cadeias de DNA se torna indispensável. Este projeto tem por objetivo o estudo de algoritmos combinatórios para rearranjo de seqüências de DNA. Um destes problemas é o de alinhamento entre duas seqüências, para o qual desenvolvemos um programa que analisa duas cadeias, buscando alinhá-las da forma que se obtenha a maior semellhança possível entre elas. Por exemplo, no estudo do código genético de duas espéies de animais, o biólogo verifica a semelhança entre fragmentos de suas cadeias de DNA. Esta tarefa é árdua (ou mesmo impossível) para ser feita manualmente pelo pesquisador que poderá fazer uso de tais programas.