Algoritmo BreakPointReversalSort

Qui di seguito verrà descritto l'algoritmo BreakpointReversalSort(π) che elimina tanti breakpoints quanto è possibile ad ogni passaggio al fine di raggiungere l'identity permutation. Successivamente verranno definite le strips per evitare l’immissione di nuovi breakpoints definendo anche dei teoremi inerenti.

BreakPointReversalSort(π)

1. while b(π) > 0

2. Tra tutte le possibili inversioni,sceglie l'inversione p che minimizza b(π ∙ p)

3. π ← π ∙ p

4. output π

5. return

Il problema con questo algoritmo non è ben chiaro perché BRS è un miglior algoritmo di approssimazione di SRS. Comunque il vero problema è che BRS può lavorare per sempre! Come possiamo essere certi del fatto che eliminando alcuni breakpoints non se introducano degli altri dando vita ad un circolo senza fine?

Definiamo strip, un intervallo tra due breakpoints consecutivi in una permutazione, e cioè ogni massimo segmento privo di breakpoints. Gli Strip si dividono in strip decrescente, striscia di elementi in ordine decrescente e strip crescente, striscia di elementi in ordine crescente. Per esempio la permutazione 0 2 1 3 4 5 8 7 6 9 consiste di 5 strips: 0, 2 1, 3 4 5, 8 7 6, e 9. Gli strips inoltre possono essere divisi in strips crescenti (3 4 5) e strips decrescenti (2 1) e (8 7 6). Una striscia costituita da un unico elemento può essere definita sia crescente che decrescente. Noi sceglieremo di definirla sempre decrescente con l’eccezione delle strips con 0 e n+1 ( che sono classificate come strips crescenti). Presentiamo dunque i seguenti teoremi in primo luogo per dimostrare che i cicli infiniti di eliminazione dei breakpoints non possono avvenire e in secondo luogo per dimostrare che la percentuale di approssimazione dell’algoritmo è 4. Sebbene la nozione di “teorema” e di “prova” può sembrare oltremodo formale per quello che in fondo è un problema biologico, è importante considerare che abbiamo modellato l’intero processo biologico in termini matematici. Stiamo provando analiticamente che l’algoritmo va incontro ad alcune aspettative. Questa nozione di prova senza sperimentazione è molto diversa da quello che normalmente un biologo intende per prova, ma diviene invece importante quando si lavora in bioinformatica. 

Ridurre il numero di breakpoints