Superstring Common più breve: trova la stringa più breve che contenga tutti i frammenti di stringa dati

12

Dati alcuni frammenti di stringhe, vorrei trovare la stringa singola più breve possibile ("stringa di output") che contenga tutti i frammenti. I frammenti possono sovrapporsi l'un l'altro nella stringa di output.

Esempio:

Per i frammenti di stringhe:

BCDA
AGF
ABC

La seguente stringa di output contiene tutti i frammenti ed è stata creata dall'appendice naive:

BCDAAGFABC

Tuttavia questa stringa di output è migliore (più breve), poiché utilizza sovrapposizioni:

ABCDAGF
^
ABC
 ^
 BCDA
    ^ 
    AGF

Sto cercando algoritmi per questo problema. Non è assolutamente importante trovare la stringa di uscita strettamente più breve, ma più breve è, meglio è. Sto cercando un algoritmo migliore di quello ovvio e ovvio che tenterebbe di aggiungere tutte le permutazioni dei frammenti di input e rimuovere le sovrapposizioni (che sembrerebbe essere NP-Completo).

Ho iniziato a lavorare su una soluzione e si sta dimostrando piuttosto interessante; Mi piacerebbe vedere cosa potrebbero venire in mente altre persone. Aggiungerò il mio work-in-progress a questa domanda tra poco.

    
posta occulus 25.09.2012 - 12:52
fonte

1 risposta

14

Quello che stai chiedendo è il problema di Short Superstring comune più breve, per il quale non esiste un algoritmo che funzioni per tutti i casi. Ma è un problema comune (in compressione e sequenziamento del DNA) e molti algoritmi di approssimazione sono ben noti.

Gli algoritmi "avidi" sono generalmente accettati come i più efficaci (in quanto hanno il peggior caso peggiore).

Leggi il documento Algoritmi di approssimazione per il problema più breve comune di superstringhe da Jonathan Turner per molte più informazioni.

    
risposta data 25.09.2012 - 13:17
fonte

Leggi altre domande sui tag