Biologia Computazionale

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