Tamanho da fonte:
Geração de matrizes de distância entre proteÃnas em placas gráficas (GPU) para estudos de filogenia molecular
Última alteração: 2012-11-13
Resumo
No estudo de filogenia é preciso construir árvores que reflitam a história evolutiva dos objetos de estudo. A construção dessas árvores baseiam-se no alinhamento de sequências de proteínas, DNA, RNA, entre outras moléculas que contém informação da evolução das espécies.
Um dos métodos utilizados para estudo de filogenia depende do alinhamento de sequências filogenéticas, que traz o desafio da escolha de quais sequências alinhar, principalmente quando estuda-se super famílias, pois nestas tem-se milhares de sequências. O que faz interessante o uso de técnicas de clusterização para dividir um grande grupo em subgrupos por similaridade.
As técnicas de clusterização utilizam matrizes de distância, que são construídas comparando cada uma das sequências com todo o grupo, para mapear as sequências de um espaço multidimensional não euclidiano para um espaço tridimensional euclidiano. As comparações realizadas entre cada uma das sequência e a totalidade do conjunto torna esses algoritmos muitos custosos em termos computacionais, tendo uma complexidade da ordem de O(n*n). De modo que pode inviabilizar o uso dessa técnica para grupos muito grandes de sequências, como as super famílias.
O algoritmo para calcular matriz de distância é inerentemente paralelo, uma vez que o cálculo da distância de um elemento para com os demais não depende do cálculo a distância de nenhum outro elemento.
As aplicações gráficas de modo geral requerem processamento paralelo e com isso as placas de vídeo (GPUs) dos computadores pessoais são desenvolvidas para esse propósito, elas contêm centenas de processadores especializados em operações de ponto flutuante além de memória mais rápida que a memória RAM convencional dos computadores.
No ano de 2007 a NVIDIA lançou o CUDA (Compute Unified Device Architecture), um modelo de programação desenvolvido para suportar a programação de conjunta de CPU e GPU, permitindo utilizar a capacidade computacional das GPUs diretamente com linguagens de programação comummente utilizadas como C/C++.
Outros trabalhos mostram que portar algorítimos paralelizáveis para a plataforma CUDA resulta em um bom ganho de desempenho. Este trabalho criou uma biblioteca em CUDA C para gerar uma matriz de distância, utilizando a distância de Levenshtein, para um conjunto de proteínas. A finalidade dessa biblioteca é ser utilizada em programas de clusterização por ser o cálculo dessa matriz um dos principais gargalos desses algoritmos.
Um dos métodos utilizados para estudo de filogenia depende do alinhamento de sequências filogenéticas, que traz o desafio da escolha de quais sequências alinhar, principalmente quando estuda-se super famílias, pois nestas tem-se milhares de sequências. O que faz interessante o uso de técnicas de clusterização para dividir um grande grupo em subgrupos por similaridade.
As técnicas de clusterização utilizam matrizes de distância, que são construídas comparando cada uma das sequências com todo o grupo, para mapear as sequências de um espaço multidimensional não euclidiano para um espaço tridimensional euclidiano. As comparações realizadas entre cada uma das sequência e a totalidade do conjunto torna esses algoritmos muitos custosos em termos computacionais, tendo uma complexidade da ordem de O(n*n). De modo que pode inviabilizar o uso dessa técnica para grupos muito grandes de sequências, como as super famílias.
O algoritmo para calcular matriz de distância é inerentemente paralelo, uma vez que o cálculo da distância de um elemento para com os demais não depende do cálculo a distância de nenhum outro elemento.
As aplicações gráficas de modo geral requerem processamento paralelo e com isso as placas de vídeo (GPUs) dos computadores pessoais são desenvolvidas para esse propósito, elas contêm centenas de processadores especializados em operações de ponto flutuante além de memória mais rápida que a memória RAM convencional dos computadores.
No ano de 2007 a NVIDIA lançou o CUDA (Compute Unified Device Architecture), um modelo de programação desenvolvido para suportar a programação de conjunta de CPU e GPU, permitindo utilizar a capacidade computacional das GPUs diretamente com linguagens de programação comummente utilizadas como C/C++.
Outros trabalhos mostram que portar algorítimos paralelizáveis para a plataforma CUDA resulta em um bom ganho de desempenho. Este trabalho criou uma biblioteca em CUDA C para gerar uma matriz de distância, utilizando a distância de Levenshtein, para um conjunto de proteínas. A finalidade dessa biblioteca é ser utilizada em programas de clusterização por ser o cálculo dessa matriz um dos principais gargalos desses algoritmos.