Soy un poco nuevo en bioinformática y trato de estudiar por mi cuenta. Estoy leyendo un libro de bioinformática: Una introducción a los algoritmos bioinformáticos y encontré algunos problemas sobre la comprensión de la prueba del algoritmo de clasificación por inversión del punto de ruptura en el capítulo 5.4.

Específicamente, el libro establece un teorema:

Si una permutación $ \ pi $ contiene una franja decreciente , luego hay una reversión $ \ rho $ que disminuye el número de puntos de interrupción en $ \ pi $ , es decir, punto de interrupción ( $ \ rho (\ pi) $ ) < breakpoint ( $ \ pi $ ) .

Este teorema garantiza que el algoritmo terminará y no conducirá a ningún punto de interrupción. Más adelante, el libro explica la prueba del teorema:

Sea $ k $ el elemento más pequeño de la franja decreciente, por lo que el elemento $ k-1 $ sería el final de una franja creciente. Por lo tanto, el elemento $ k $ y $ k-1 $ corresponde a un punto de interrupción. Luego, invertir el segmento entre $ k $ y $ k-1 $ reducirá el número de puntos de interrupción.

Estoy bastante confundido acerca de esta prueba y realmente no entiendo lo que los autores quieren decir al invertir el segmento entre $ k $ span > y $ k-1 $ . ¿Alguien puede explicarme la prueba?

Aquí está la diapositiva de la conferencia sobre ordenamiento inverso que se basa en el libro http://csbio.unc.edu/mcmillan/Media/Lecture07Spring2015.pdf.