Alinhamentos de seqüencias em bioinformática
Olá pessoal, é com grande prazer que inicio minhas postagens neste blog. E para inaugurar vou deixar um texto sobre o foco da minha área de pesquisa no mestrado: alinhamento de seqüências em bioinformática. Encontrei em minhas anotações esse texto e achei interessante compartilhar com vocês. Espero que ele consiga mostrar àqueles que não conhecem a fundo a grande importância dos alinhamentos nessa área.
Alinhamentos de seqüencias em bioinformática
Os avanços recentes na biologia molecular e nas pesquisas genômicas, em particular no desenvolvimento de técnicas de sequenciamento de DNA, tem gerado uma imensa quantidade de dados, que geralmente consistem em seqüências de DNA e de proteínas. A existência e o rápido crescimento dessa grande massa de dados nos levaram ao uso indispensável de computadores e na descoberta de técnicas para resolver os problemas mais complexos da biologia molecular. Um desses problemas é o alinhamento simultâneo de várias seqüências que apresentem resultados biológicos precisos em um tempo viável de computação.
Para resolver este problema algumas abordagens surgiram. Basicamente, elas se baseiam em dois métodos principais: programação dinâmica e métodos heurísticos.
O primeiro calcula o melhor alinhamento possível entre as seqüências. Ele se baseia na construção de uma matriz de comparação de prefixos das seqüências a serem alinhadas. No entanto, o problema de se utilizar programação dinâmica para alinhar um número n qualquer de seqüências é NP-Completo. Esses problemas não possuem solução conhecida que apresente uma resposta em um tempo polinomial ou menor com relação ao tamanho da entrada de dados. Isto significa que o tempo de processamento é muito alto, tornando-se impraticável.
Para resolver este problema, algumas heurísticas foram desenvolvidas, de forma a diminuir a complexidade de tempo de alinhamentos com mais de duas seqüências. As abordagens utilizando grafos de ordem parcial, métodos de caminho euleriano e colônia de formigas são alguns exemplos. No entanto, a mais freqüentemente utilizada é o alinhamento múltiplo progressivo. Este foi descrito em várias formas, por vários grupos distintos, o que resultou em uma série de programas a partir da segunda metade dos anos 80, e que ainda são utilizados atualmente.
O alinhamento múltiplo progressivo permite que alinhamentos de seqüências pouco relacionadas sejam rapidamente construídos e de uma forma muito simples. Ele é baseado na construção do alinhamento de forma gradual, usando uma estrutura de árvore para guiar os alinhamentos. Ele está implementado nos programas mais utilizados atualmente, como o ClustalW, o MAFFT e o MUSCLE.
Um abraço a todos e até o próximo post.
Alinhamentos de seqüencias em bioinformática
Os avanços recentes na biologia molecular e nas pesquisas genômicas, em particular no desenvolvimento de técnicas de sequenciamento de DNA, tem gerado uma imensa quantidade de dados, que geralmente consistem em seqüências de DNA e de proteínas. A existência e o rápido crescimento dessa grande massa de dados nos levaram ao uso indispensável de computadores e na descoberta de técnicas para resolver os problemas mais complexos da biologia molecular. Um desses problemas é o alinhamento simultâneo de várias seqüências que apresentem resultados biológicos precisos em um tempo viável de computação.
Para resolver este problema algumas abordagens surgiram. Basicamente, elas se baseiam em dois métodos principais: programação dinâmica e métodos heurísticos.
O primeiro calcula o melhor alinhamento possível entre as seqüências. Ele se baseia na construção de uma matriz de comparação de prefixos das seqüências a serem alinhadas. No entanto, o problema de se utilizar programação dinâmica para alinhar um número n qualquer de seqüências é NP-Completo. Esses problemas não possuem solução conhecida que apresente uma resposta em um tempo polinomial ou menor com relação ao tamanho da entrada de dados. Isto significa que o tempo de processamento é muito alto, tornando-se impraticável.
Para resolver este problema, algumas heurísticas foram desenvolvidas, de forma a diminuir a complexidade de tempo de alinhamentos com mais de duas seqüências. As abordagens utilizando grafos de ordem parcial, métodos de caminho euleriano e colônia de formigas são alguns exemplos. No entanto, a mais freqüentemente utilizada é o alinhamento múltiplo progressivo. Este foi descrito em várias formas, por vários grupos distintos, o que resultou em uma série de programas a partir da segunda metade dos anos 80, e que ainda são utilizados atualmente.
O alinhamento múltiplo progressivo permite que alinhamentos de seqüências pouco relacionadas sejam rapidamente construídos e de uma forma muito simples. Ele é baseado na construção do alinhamento de forma gradual, usando uma estrutura de árvore para guiar os alinhamentos. Ele está implementado nos programas mais utilizados atualmente, como o ClustalW, o MAFFT e o MUSCLE.
Um abraço a todos e até o próximo post.
1 comentários:
Muito bom seu post, estou realizando minha monografia, e preciso comentar sobre o Problema NP-completo e sobre os principais programas que realizam o alinhamento múltiplo. Utilizei na metodologia da minha monografia o PRANKSTER, você sabe se ele não tem esse problema?
Postar um comentário