-
-
- ALBERTO CAPRARA, ROMEO RIZZI,
Improved Breakpoint Graph Decompositions,
submitted
descrizione:
Il sorting by reversals é uno di quei
problemi in biologia computazionale
che sono venuti alla
luce con lo sviluppo del Progetto Genoma Umano.
L'interesse per questo problema da parte
della biologia computazionale é forte.
Caprara aveva purtroppo dimostrato che il problema
era NP-hard.
Sorge a questo punto l'interesse per degli algoritmi
di tipo approssimato.
Questi sono intesi a produrre delle soluzioni che, se non ottime,
siano quantomeno di provata qualitá,
ossia di qualitá superiore ad un certo bound fissato.
Noi si é migliorato il miglior
bound attuale.
Il tutto a prezzo di un'analisi combinatorica
di non poco peso per il lettore e per chi mai
volesse implementare l'algoritmo.
La complessitá computazionale dell'algoritmo
tuttavia non ne ha sofferto.
Amsterdam,
November 1999.
Romeo Rizzi
2000-02-14
|
© Dipartimento di Matematica - Università di Trento
|