[SP-pm] Bioinformática e Sequenciamento [Was: ordenando arquivos.]

Bruno Buss bruno.buss at gmail.com
Fri Jul 29 19:58:45 PDT 2011


2011/7/29 Stanislaw Pusep <creaktive at gmail.com>

> Perlssoal, não sei se isso tem a ver com o tópico, mas tenho a seguinte
> coleção de strings (1 por linha):
>
> <html><head><title>teste 1</title></head><body><h1>teste
> 1</h1>qwerty</body></html>
> <html><head><title>teste 2</title></head><body><h1>teste
> 2</h1><h2>subtitulo</h2>asdfghj</body></html>
> <html><head><title>404</title></head><body>not found</body></html>
>
> Quero obter a seguinte estrutura (espécie de grafo):
>
>                                                                      -
> teste 1 -           ---------- qwerty -----------
>                                                                     /
>     \         /                             \
>                       - teste 1 -                           - <h1> -
>       - </h1> -                               -
>                      /           \                         /        \
>     /         \                             / \
> <html><head><title> --- teste 2 --- </title></head><body> -          -
> teste 2 -           - <h2>subtitulo</h2>asdfghj -   - </body></html>
>                      \           /                         \
>                                                /
>                       --- 404 ---
> ------------------------- not found --------------------------
>
> Estou ciente de que, se eu empregar grafo "as is", a minha RAM vai estourar
> logo na home do UOL, a menos que eu "tokenize" por tags ou algo do gênero :/
>

Pelo o que entendi, não... o seu problema não é o mesmo do tópico (mas é
mais por causa que não entendi qual era o problema original do tópico ainda,
estou esperando o e-mail do Thiago explicando para que serve a ordenação)...
apesar que o seu problema tem alguns equivalentes em bioinfo.

Sobre o seu problema, talvez o que você queira é algo como um algoritmo de
distância de edição:
http://en.wikipedia.org/wiki/Levenshtein_distance

O problema desse tipo de algoritmo é que ele é O(mn), logo com duas strings
grandes a sua complexidade vai crescer rapidamente.
Outro problema é que para conseguir esse tipo de output você vai precisar
guardar a matriz toda da PD (ou quase toda... mas mesmo assim ainda é muita
coisa).
E por fim... não me recordo agora uma forma - simples - de comparar as 3
strings em um só algoritmo... a não ser talvez adicionar mais uma dimensão a
matriz de PD.

Só mais uma coisa... eu não entendi o que você quis dizer com " grafo "as
is" ". Seria cada char um nó do grafo ou coisa parecida? Se sim... o
algoritmo de distância de edição, a PD em si, pode ser modelada como um
grafo desse jeito (e como você mesmo disse, para strings grandes... vai
faltar memória).

[ ]'s
-- 
Bruno C. Buss
http://brunobuss.wordpress.com/
http://www.dcc.ufrj.br/~brunobuss/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20110729/89e86d83/attachment.html>


More information about the SaoPaulo-pm mailing list