Il problema della massima sottosequenza comune (LCS, longest common subsequence) consiste nel trovare la più lunga sottosequenza comune a tutte le stringhe in un insieme di stringhe (solitamente due). Si noti che una sottosequenza non è necessariamente una sottostringa.
Questo problema, classico tra i problemi informatici , trova applicazione in bioinformatica oltre ad essere anche la base di "diff" (un software di comparazione di file).
Esempio Considerando le sequenze ABCD e ACBAD, esse hanno cinque sottosequenze comuni di lunghezza 2: AB, AC, AD, BD, e CD; due di lunghezza 3: ABD e ACD; e nessuna sottosequenza comune più lunga. Quindi ABD e ACD sono le loro sottosequenze comuni massime.
Complessità
Nel caso generale di un numero arbitrario di sequenze in input, il problema è NP-hard. Se il numero di sequenze è costante, il problema può essere risolto in tempo polinomiale mediante programmazione dinamica.
Note
Categoria:Problemi NP-completi Categoria:Programmazione dinamica