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

[Bruno Buss]

2011/8/2 Stanislaw Pusep <creaktive at gmail.com>

> Bruno, tanto LCS quanto LCSS fazem comparação de 2 em 2, certo? Ao menos,
> pela implementação "naive", que monta uma matriz... Já pelo conceito
> do Generalised suffix tree, daria para "comparar" 3 ou mais, não?


LCS e LCSS são problemas "genéricos", não estão limitados a quantidade de
strings.

A solução que utiliza uma matriz s1*s2, é uma abordagem por programação
dinâmica e não tenho certeza se a generalização para mais de 2 strings é de
fato trivial.

Mas utilizando estruturas de dados melhores, como por exemplo a árvore se
sufixo, com certeza é generalizado para n strings.
(Mas a complexidade acaba sendo praticamente a mesma, produtório dos
tamanhos das strings)

[ ]'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/20110802/a6aa15a5/attachment.html>