Tese relaciona material genético do homem e do chimpanzé e comprova viabilidade do uso de algoritmos exatos para alinhamento de sequências biológicas longas

Arte: Marcelo Jatobá/Secom UnB


Mais uma barreira ao progresso da Biologia Molecular e da Genética foi superada: pela primeira vez, realizou-se a comparação de todos os cromossomos homólogos do homem e do chimpanzé por meio de algoritmos exatos. A conquista está registrada na tese de doutorado Algoritmos Paralelos Exatos e Otimizações para Alinhamento de Sequências Biológicas Longas em Plataformas de Alto Desempenho, de  Edans Flávius de Oliveira Sandes, agraciada com o Prêmio Capes de Tese 2016 e a segunda edição do Prêmio UnB de Dissertação e Tese.

 

"O objetivo do meu trabalho foi comparar todos os cromossomos do homem com os do chimpanzé utilizando algoritmos exatos. Mas, se executado da maneira convencional, seria necessário muito tempo para obter resultado. A comparação de um único cromossomo, por exemplo, poderia demorar até mais de um ano", afirma Sandes. De acordo com o estudioso, esse método é usado para sequências menores, como vírus, que em média possuem cerca de mil caracteres. “O menor cromossomo humano tem mais de 20 milhões de caracteres. Para alinhar uma sequência com um milhão de pares de bases, por exemplo, seria preciso um terabyte de memória da plataforma”, exemplifica. Para solucionar o impasse no uso de algoritmos exatos, ele iniciou a pesquisa de métodos que poderiam tornar o processamento mais rápido.

 

O pesquisador esclarece que os algoritmos exatos foram propostos desde 1970, buscando o resultado ótimo no alinhamento de duas sequências biológicas. Contudo, por demandarem alto poder de processamento e grande quantidade de memória da plataforma, seu uso foi apontado na literatura científica como impraticável para sequências muito longas de DNA, tais como os cromossomos humanos. Por isso, foram desenvolvidos os algoritmos heurísticos, que aceleram esse processo e retornam com bom resultado, embora não garantam o resultado ótimo.

Pesquisador Sandes e orientadora Alba Melo, no Laboratório de Sistemas Concorrentes e Integrados da UnB, com a primeira placa gráfica utilizada na pesquisa. Foto: Júlio Minasi/Secom UnB

 

ENTENDA – O estudo comparativo do DNA de seres humanos com o de chimpanzés é recorrente dada à similaridade desses dois organismos. Assim, a análise do genoma, além de possibilitar estudos evolutivos, permite formular hipóteses sobre doenças que existem apenas para uma das espécies e sua ligação com determinadas partes da sequência genética. Obter tais dados só é possível graças a ferramentas e algoritmos desenvolvidos na área de Bioinformática. Uma das operações básicas feita por computadores é a comparação do genoma de diferentes organismos para verificar o grau de similaridade entre as sequências e mapear as regiões onde acontecem as semelhanças ou divergências. Nesse processo, havia sido convencionada a utilização de algoritmos heurísticos em casos de sequências longas.

 

Contudo, em sua tese, Sandes comprovou que é possível fazer comparações de sequências genômicas longas, em tempo viável, utilizando o algoritmo exato Smith-Waterman. “Comparamos todos os cromossomos homólogos do homem e do chimpanzé. Para o maior cromossomo, gastamos menos de duas horas. Assim, nas condições em que trabalhamos, é possível chegar a esses resultados em poucos dias. Anteriormente isso levaria anos”, ressalta o pesquisador. 

 

A orientadora da tese e professora titular da UnB, Alba Cristina Melo, explica que o diferencial dessa pesquisa foi abordar a questão por duas frentes: criar variantes otimizadas do algoritmo e viabilizar sua aplicação em diferentes plataformas. “A matriz a ser calculada pelo algoritmo envolve milhões de caracteres, totalizando petabytes de memória. É algo enorme e por isso demora muito. A estratégia do Edans foi se perguntar se seria necessário calcular a matriz toda ou se mesmo deixando de calcular algumas partes seria possível obter o melhor resultado. Então ele elaborou uma técnica chamada Block Pruning e verificou que alguns blocos de células dessa matriz poderiam ser desconsiderados e ainda se chegaria ao resultado ótimo”, explica a docente.

 

Sandes esclarece que na literatura existem alguns conceitos que abordam esse descarte de células da matriz. Contudo, ele buscou otimizar esse descarte, focando não apenas uma célula, mas uma região maior de blocos. "Fizemos estimativas, dadas algumas condições específicas de qual seria a área descartada. Desenhando geometricamente, traçando algumas linhas, delimitando intercessões, identificamos a área da matriz a ser desconsiderada”, detalha. Além disso, ele otimizou a técnica para que outros pesquisadores possam utilizá-la, bastando uma pequena implementação do código de acordo com a plataforma adotada.

 

Somado ao descarte de células, o pesquisador testou outros recursos. “Começamos a pesquisar métodos para deixar o processamento mais rápido. Na nossa área, um dos recursos que utilizamos é o processamento distribuído, que consiste em vários computadores processando conjuntamente uma mesma tarefa. Assim, buscamos usar todo o poder computacional para obter um resultado mais rápido”, explica.

 

Para acelerar o tempo demandado, Sandes adotou unidades de processamento gráfico conhecidas como GPUs (sigla em inglês para Graphics Processing Unit) e também passou a usar o procedimento chamado execução especulativa. “Empregamos várias GPUS que processam simultaneamente com base no melhor resultado local. Assim, quando uma GPU recebe o resultado da anterior, ela faz uma comparação. Se ela tiver trabalhado até então com um resultado errado, ela o descarta e processa novamente. Mas se o resultado for o correto, então ela economizou tempo, pois já terá processado a resposta. Essa técnica se mostrou positiva, nesse caso, porque as sequências trabalhadas eram muito similares. Então, o melhor resultado específico foi, na maioria das vezes, o melhor resultado global e acelerou o processamento", esclarece Sandes.

 

Todas as técnicas elaboradas na tese foram implementadas e integradas na ferramenta de código aberto chamada CUDAlign, disponibilizada gratuitamente na Internet por meio do site Github.

 

PARCERIAS – Para executar o alinhamento de sequências genéticas tão longas, foi preciso usar plataformas de alto desempenho, também conhecidas como supercomputadores. Na Espanha, o pesquisador pôde passar alguns meses na Universidade Politécnica da Catalunha, em Barcelona, onde dispunha da estrutura necessária para a pesquisa. Em seguida, obteve acesso ao supercomputador Keeneland Full Scale System, na Georgia, Estados Unidos.

 

A experiência fora do Brasil agregou ao trabalho novas demandas. "Para conseguir bom desempenho, às vezes temos que fazer algo muito específico e, por isso, nosso código rodava somente em uma marca de placa de vídeo. Mas a equipe de Barcelona usava outro ambiente de programação. Então, começamos a trabalhar em conjunto para viabilizar uma execução em múltiplas plataformas”, acrescenta.

 

Segundo a orientadora, a tese abriu diferentes caminhos para novas pesquisas. "Já tenho um aluno de graduação, dois de mestrado e um de doutorado que estão pesquisando desdobramentos desse trabalho. Agora buscamos parcerias com biólogos especialistas em cromossomos humanos para analisar os resultados que obtivemos. Também buscamos parceria para fazer uma análise estatística. Queremos ver o impacto disso nas pesquisas, mas por ser um assunto de diferentes áreas, é algo mais demorado”, ressalta.

 

A colaboração internacional segue firme, com pesquisas sobre o Block Pruning sendo aplicado para cortar áreas maiores da matriz, e outra abordagem verificando se houve aumento no consumo de energia com o método proposto. Sandes conta que sua maior satisfação é ver esse desdobramento do trabalho. "Vejo que essa pesquisa não para comigo, mas vai adiante. Na ciência a gente sempre sobe um degrau por vez. Fizemos um método mais rápido de execução, mas não sabemos o que isso pode gerar daqui para frente. Quem sabe possa até chegar à cura de determinada doença. Mesmo que seja algo indireto, espero que colabore para novos resultados", conclui o doutor premiado.

 

ATENÇÃO – As informações, as fotos e os textos podem ser usados e reproduzidos, integral ou parcialmente, desde que a fonte seja devidamente citada e que não haja alteração de sentido em seus conteúdos. Crédito para textos: nome do repórter/Secom UnB ou Secom UnB. Crédito para fotos: nome do fotógrafo/Secom UnB.