Alinhamento múltiplo de seqüências utilizando otimização dialética

Abstract

Este trabalho propõe uma abordagem baseada no método dialético de otimização para resolver o problema do alinhamento múltiplo de sequências (MSA). Nesta abordagem, problemas de múltiplo alinhamento de sequências são vistos como problemas de otimização, onde os candidatos à solução são modelados como vetores cujas componentes representam as posições das lacunas ao longo das sequências. Além disso, os candidatos a solução são avaliados através de uma função objetivo que é sugerida como uma composição de funções para pontuação de correspondências, funções para penalização e pontuação por aspectos desejados e não-desejados. Com o objetivo de testar computacionalmente esta proposta, foram criados um conjunto sintético de dados, composto de 50 grupos de 4 sequências e um modelo equivalente baseado em algoritmos genéticos. A representação de candidatos à solução baseada em posições trouxe um problema com relação à quantidade de lacunas que deveria ser utilizada no alinhamento de cada um dos 50 grupos de sequências. Como solução, a ferramenta ClustalW foi aplicada, em cada grupo de sequências, para produzir um alinhamento múltiplo, o qual foi utilizado para fornecer informações sobre a quantidade de lacunas utilizada. Os alinhamentos realizados pelo ClustalW também foram avaliados pela função objetivo proposta, para a produção de resultados comparáveis. Os experimentos foram definidos sob três abordagens quanto ao número de lacunas utilizado. Na primeira abordagem, para o alinhamento de cada grupo de sequências foi utilizada uma quantidade fixa de lacunas e equivalente à metade do comprimento das sequências, enquanto que na segunda abordagem, foi utilizada um número de lacunas igual ao usado pelo ClustalW. Na terceira abordagem, o número de lacunas usado por cada candidato à solução existente da população inicial foi definido com um valor escolhido aleatoriamente entre os valores que correspondem a 5% e 50% do comprimento. A cada abordagem, os experimentos foram refeitos utilizando-se uma variação na qual o alinhamento produzido pelo Clustal era inserido foi população inicial, em um processo conhecido como semeadura. Todos os experimentos foram primeiramente realizados utilizando o modelo alternativo, baseado em algoritmos genéticos, a fim de validar representação e função objetivo sugeridas, e, foram refeitos em seguida utilizando o método baseado em otimização dialética. Os resultados obtidos por ambos modelos foram comparados com os resultados obtidos pelos alinhamentos produzidos pelo ClustalW através do teste não-paramétrico de Wilcoxon para amostras pareadas. Em comparação com o algoritmo ClustalW, o modelo baseado no método dialético de otimização provou ser capaz de produzir alinhamentos de altos scores como também de realizar melhorias significativas nos alinhamentos encontrados pelo ClustalW.