Análise e Projetos de Algoritmos para a Bioinformática
MEDICINA VETERINÁRIA
CAIO CESAR ROCHA MENDES
Técnicas de análises e Projetos de Algoritmos aplicados à bioinformática
Belém
2010
CAIO CESAR ROCHA MENDES
Técnicas de análises e Projetos de Algoritmos aplicados à bioinformática
Resenha apresentada à Universidade Federal Rural da Amazônia ao Curso de Medicina Veterinária como requisito à obtenção da 1ª Nota Parcial (NAP1) da disciplina Bioinformática ministrada pelo Prof. Eng. D.Sc. Emerson Cordeiro Morais.
Belém
2010
1. INTRODUÇÃO
Antes de abordar a temática "Técnicas de análises e projetos de algoritmos aplicados à bioinformática" precisa-se ter em mente, primeiramente, o conceito da palavra algoritmo. Etimologicamente a palavra algoritmo origina do sobrenome Al-Khwarizmi, de um famoso matemático persa do século IX chamado Mohamed bem Musa. Porém alguns estudiosos afirmam que a palavra origina do termo Al-Goreten.
Conceitualmente, para CASTIÑEIRA, na obra "Análise de Algoritmos", entende-se algoritmo como uma sequência finita e ordenada de procedimentos necessários para a resolução de uma problemática bem formulada, possível de ser aplicada em computador, que sempre termina num determinado período de tempo, produzindo o resultado ou indicando a impossibilidade de obtenção do mesmo.
O conceito de algoritmo é utilizado em praticamente todas as áreas do conhecimento, apenas mudando a nomenclatura em vigência. Por exemplo, cita-se o "Plano de Ação" frequentemente utilizado em áreas como a administração e a contabilidade que nada mais é do que um conjunto de soluções para um determinado problema, visando obter um resultado satisfatório, ou seja, um algoritmo.
No material "Lógico em Algoritmos", segundo COSTA (2005), todo algoritmo apresenta características básicas que devem ser levadas em consideração. Um algoritmo deve sempre partir de um ponto inicial e chegar a um ponto final; não deve ser ambíguo, ou seja, dar margem a várias interpretações; em alguma parte do programa, todas as suas etapas devem ser alcançadas.
2. A BIOINFORMÁTICA
A bioinformática é hoje uma ciência em pleno crescimento. A alta oferta de empregos na área é notória, haja vista a quantidade exorbitante de informações genômicas produzidas. Devido à velocidade do crescimento dos estudos e informações referentes a esta promissora área, a própria conceituação de bioinformática teve que ser reformulada com o passar do tempo, de forma que ela viesse a englobar as diversas áreas pesquisadas nesse campo do conhecimento.
De acordo com as obras "Artificial Intelligence in Bioinformatics (Editorial) Computers and Chemistry" e "Earliest pages in bioinformatics, Bioinformatics", o termo bioinformática, em sua origem, fazia referência à análise de sequências de dados de proteínas e do DNA (CORNE AND MARTIN, 2001) (TRIFONOV, 2000). Nos últimos anos o termo foi modificado de maneira a acrescentar todos os aspectos da biologia molecular desde a análise seqüencial de aminoácidos até a análise de estrutura de proteínas, predição e modelamento de processos celulares, passando por análise de textos e armazenamento de dados (CORNE AND MARTIN, 2001).
Portanto, conclui-se no artigo "What is Bioinformatics" que a bioinformática pode ser observada como uma junção entre a biologia molecular e a ciência da computação (BIOPLANET, 2002).
2. A UTILIZAÇÃO DE ALGORITMOS NA BIOINFORMÁTICA
Falando sobre a relação entre a computação e a biologia, em seu material didático "Ferramentas de Bioinformática: Manipulação de sequências e recuperação de regiões flanqueadoras de um alvo" RIBEIRO afirma que o envolvimento de técnicas computacionais, com destaque ao desenvolvimento de algoritmos eficientes torna-se indispensável para uma boa análise de dados gerados, e assim, consequentemente, gerando a finalização com sucesso de cada projeto.
Ainda para o autor, a biologia molecular em parceria com a genética é a área que mais faz uso de técnicas computacionais, das quais destaca-se a teoria da computação, principalmente através da formulação de algoritmos a fim de solucionar diversos problemas surgidos nos últimos anos no campo biológico.
A computação, assim como a genética, evoluiu de forma considerável, fato este que provocou o surgimento de diferentes áreas de estudos e técnicas, dentre elas a bioinformática.
3. ANÁLISE DE ALGORITMOS
Tendo em vista o conceito anteriormente abordado referente a algoritmos, LESK (2005) no livro "Introduction to Bioinformatics" afirma que: "Para a recuperação de seqüências semelhantes, precisamos medir a semelhança da sequência sonda com cada sequência do banco de dados. É possível fazer muito melhor do que a solução simples de checar cada par de posições em cada justaposição possível, um método que, mesmo sem permitir a inserção de lacunas, exigiria um tempo proporcional ao produto do número de caracteres na seqüência sonda pelo número de caracteres no banco de dados. Uma especialização da ciência da computação, conhecida vulgarmente como "stringology", concentra-se no desenvolvimento de métodos ecientes para este tipo de problema, analisando seus desempenhos efetivos".
Segundo FEOFILOFF (2010), "A análise de algoritmos estuda a correção e o desempenho de algoritmos. Em outras palavras, a análise de algoritmos procura respostas para perguntas do seguinte tipo: Este algoritmo resolve o meu problema? Quanto tempo o algoritmo consome para processar uma 'entrada' de tamanho n?". Além disso, a análise de algoritmos estuda certos paradigmas (como divisão-e-conquista, programação dinâmica, gula, busca local, aproximação, etc.) que se mostraram úteis na criação de algoritmos para vários problemas computacionais.
4. PROJETOS OU PARADIGMAS DE ALGORITMOS
4.1 DIVISÃO E CONQUISTA
ZIVIANI (2004), em sua obra "Projeto de Algoritmos com Implementações em Pascal e C ? 2ª .Edição", afirma que "A técnica de Divisão e Conquista consiste em dividir uma problemática recursivamente em subproblemáticas menores, até que estas possam ser solucionadas diretamente. Porém, a solução do problema inicial é dada através da combinação dos resultados de todos os problemas menores calculados.Vários problemas podem ser solucionados através desta técnica, como o da ordenação de números através do algoritmo Mergesort, ou Quicksort e da transformação discreta de Fourier através da transformada rápida de Fourier".
OLIVEIRA (2006) afirma que muitas problemáticas podem ser desvendadas pela decomposição e recombinação de subproblemas que são parecidos com o problema original. A autora fala ainda que: "A abordagem de divisão e conquista para a resolução de problemas, fornece um método poderoso para o projeto de algoritmos. A idéia básica da divisão e conquista é dividir um problema em subproblemas menores independentes, resolvê-los e combinar as soluções obtidas em uma solução para o problema original. Algoritmos de divisão e conquista são geralmente recursivos".
3.2 ALGORITMOS GANANCIOSOS OU GULOSOS
Segundo FEOFILOFF (2010) para solucionar um problema, um algoritmo guloso faz a escolha, em cada iteração, do objeto mais "apetitoso" que encontra pela frente. (A definição de "apetitoso" é estabelecida a priori.). O objeto escolhido passa a fazer parte da solução que o algoritmo constrói.
Já ZIVIANI (2004), na obra citada anteriormente, afirma que um algoritmo que usa estratégia gananciosa, faz sempre escolhas que, naquele instante, parecem excelentes. Isto pode levar a uma solução ótima, ou não, mas provavelmente não vai levar a uma solução insatisfatória. Pode-se citar como um exemplo de algoritmo guloso a situação onde ao se fazer o caminhamento em um grafo orientado com pesos nas arestas, deve-se escolher sempre o caminho de menor peso de uma aresta para outra, afim de encontrar o caminho menos extenso entre duas arestas nesse grafo.
Ainda para o autor, "Um algoritmo guloso é "míope": ele toma decisões com base nas informações disponíveis na iteração corrente, sem olhar as consequências que essas decisões terão no futuro. Um algoritmo guloso jamais se arrepende ou volta atrás, ou seja, as escolhas que faz em cada iteração são definitivas".
Embora algoritmos gananciosos pareçam necessariamente corretos, a prova de sua correção é, em geral, muito sutil. Para compensar, algoritmos gulosos são extremamente velozes e eficientes. (É preciso dizer, entretanto, que os problemas que admitem soluções gulosas são um tanto raros.).
3.3 PROGRAMAÇÃO DINÂMICA
Diversos algoritmos eficientes seguem o projeto da programação dinâmica. Esse método de projeto de algoritmos, ou paradigma, é uma espécie de tradução iterativa inteligente da recursão e pode ser definido, vagamente, como "recursão com apoio de uma tabela".
Como em um algoritmo recursivo, cada fase do problema é resolvida a partir da solução de fases menores, ou melhor, de sub-fases da etapa original. A característica distintiva da programação dinâmica é a tabela que armazena as soluções das várias sub-fases. O consumo de tempo do algoritmo é, em geral, proporcional ao tamanho da tabela.
Para PARBERRY (1995) no artigo "Problems on Algorithms", Programação Dinâmica é um nome fantasia para recursão com uma tabela. Em vez de resolver os subproblemas recursivamente, resolve seqüencialmente e armazena as suas soluções em uma tabela. O truque é resolvê-los na ordem certa para que sempre que a solução para um subproblema seja necessária, já esteja disponível na tabela. A programação dinâmica é particularmente útil em problemas para os quais dividir e conquistar aparecem como um número exponencial de subproblemas. Neste caso, faz sentido para calcular cada solução a primeira vez e guardá-la em uma tabela para uso posterior, em vez de refazer ele recursivamente cada vez que for necessário.
4. CONCLUSÃO
Através da leitura das obras anteriormente citadas que abordam a temática "Técnicas de análises e projetos de algoritmos aplicados à bioinformática", percebe-se o quão importante é a inserção da computação, principalmente com a utilização de projetos de algoritmos para o desenvolvimento da Biologia molecular, com destaque para a Genética. Os métodos de análise e projetos de algoritmos citados (Divisão e Conquista, Algoritmos Gulosos e Programação Dinâmica) ajudam a tornar os processos mais práticos, dinâmicos e confiáveis.
Durante o estudo observou-se que para resolver um determinado problema no computador é necessário que seja, a priori, encontrada uma forma de descrever este problema de uma forma clara e precisa. É preciso que encontremos uma seqüência de procedimentos que possibilitem que o problema possa ser resolvido de maneira automática e repetitiva. Além disso, precisa-se definir como as informações que serão processadas serão armazenadas no computador. Portanto, a solução de um problema pela computação é baseada em duas etapas: a seqüência de passos e a forma como os dados serão guardados no computador.
Pode-se perceber também os notórios avanços nos estudos referentes à Bioinformática. Diversos algoritmos foram elaborados visando suprir a necessidade crescente de se fazer estudos mais complexos para a Biologia. Cada vez mais estes algoritmos são capazes de manipular exorbitantes volumes de informações de seqüências de genoma humano e polimorfismos.
Estudos ainda mais complexos sobre a Biologia provavelmente surgirão. Então cabe à computação dar o suporte para que avanços provenientes dessas pesquisas tornem-se possíveis. Eis aí a grande função da Bioinformática, garantir e possibilitar cada vez mais os avanços tecnológicos e científicos para os estudos biológicos.
5. REFERÊNCIAS BIBLIOGRÁFICAS
- BIOPLANET. What is Bioinformatics (2002). Disponível em: http://www.bioplanet.com/whatis.html. Acesso em: 25 Set. 2010
- CASTIÑEIRA, Maria Inês. Análise de Algoritmos. Disponível em: . Acesso em: 25 Set. 2010.
- CORNE, D. W. and MARTIN, A. C. R. (2001) Artificial Intelligence in Bioinformatics (Editorial) Computers and Chemistry 26, 1-3. Special issue edited by Martin and Corn.
- COSTA, F. F. C. Lógica e Algoritmos - Parte 1 . Disponível em: . Acesso em: 24 Set. 2010.
- FEOFILOFF, Paulo. Disponível em: . Acesso em: 24 Set. 2010.
- LESK. A. M. Introduction to Bioinformatics. 2. ed. New York: Oxford University Press, 2005. 360 p.
- OLIVEIRA S.R.F. Análise e desenho de algoritmos. São Paulo. Disponível em: . Acesso em: 25 Set. 2010.
- PARBERRY, Ian. Problems on Algorithms, Prentice Hall, 1995.
- RIBEIRO, Diógenes. C. D. Ferramentas de Bioinformática: Manipulação de sequências e recuperação de regiões Flanqueadoras de um alvo. Disponível em: . Acesso em: 24 Set. 2010.
- TRIFONOV, E. N. (2000). Earliest pages in bioinformatics, Bioinformatics 16: 5_9.
- ZIVIANI, N. Projeto de Algoritmos com Implementações em Pascal e C ? 2ª .Edição. Editora Thomson, São Paulo, 2004.
Autor: Caio Mendes
Artigos Relacionados
Aprofundando Os Conhecimentos De Grafo Com O Google Earth
Análise De Componente Principal (pca) E Classificação Através De Clustering
Algoritmos: Quanto Mais Cedo Aprende-los Melhor.
Criptografia QuÂntica
Leis Da Robótica
Método Simplex
MemÓria Virtual (paginaÇÃo E SegmentaÇÃo)