Um problema que aparece com certa frequência quando trabalhamos com informações textuais é a necessidade de comparar uma string com a outra. Imediatamente podemos imaginar que este é um problema de solução trivial, onde basta fazer:
>> stringA == stringB
e avaliar se o resultado foi True ou False. De fato, se desejamos saber se uma string é exatamente igual a outra, esta seria uma solução. Porém, não é a solução mais adequada para a maioria do problemas.
Quando falamos em correção automática de textos (muito comum hoje em dia nos nossos smartphones), comparação entre sequências de DNA e reconhecimento de caracteres, não basta apenas ter uma resposta do tipo True ou False. A resposta que queremos é o percentual de similaridade entre as duas strings.
Segundo um artigo no Wikipedia, uma sequência de DNA ou sequência genética é uma série de letras representando a estrutura primária de uma molécula ou cadeia de DNA, real ou hipotética, com a capacidade de carregar informação. As letras possíveis são A, C, G e T, representando os quatro nucleotídeos (subunidades) de uma cadeia de DNA – as bases adenina, citosina, guanina, timina, com ligação covalente a uma "coluna vertebral" de fósforo.
Sob este contexto, vamos analisar como calcular a similaridade entre duas sequências de DNA geradas no Python. Primeiramente, vamos gerar duas sequências aleatórias de DNA, com 16 nucleotídeos cada. Utilizamos o módulo random para criar a função abaixo:
>> import random
>> def DNA(length):
>> return ''.join(random.choice('CGTA') for nucleot in xrange(length))
Em seguida, utilizamos o módulo difflib, também já nativo do Python, para calcular a função de similaridade.
>> import difflib
>>#Modulo o DIFFLIB
>>s = difflib.SequenceMatcher(None, DNA1, DNA2)
>> s.find_longest_match(0,len(DNA1),0,len(DNA2)) #Retorna a quantidade de caracteres semelhantes
>> difflib.SequenceMatcher(None, DNA1, DNA2).ratio() #Retorna o indice de similaridade
Vemos que exite aproximadamente 47% de similaridade entre as duas sequências. Esta medida é muito relevante em diversas aplicações de mineração de textos, podendo ser usada até como variável preditora ou medida de segmentação.
No Github você pode fazer o download do código completo -> similarString.py
O princípio para o cálculo da similaridade é a Distância de Levenshtein. Ela é a medida que calcula a diferença entre duas sequências, baseada no número de caracteres mínimos que devem ser mudados para transformar uma sequência em outra. Ou seja, ela considera as operações básicas de inserção, substituição e eliminação de caracteres para calcular o quão distantes uma sequência está da outra. Um exemplo considerando a palavra caro:
substituição: caro -> cara
eliminação: caro -> car
Uma explicação mais aprofundada é encontrada em http://en.wikipedia.org/wiki/Levenshtein_distance
Um abraço e até o próximo post!
0 comentários:
Postar um comentário