Los puntos clave no están disponibles para este artículo en este momento.
Los estudios de genomas que evolucionan por reorganizaciones conducen a un problema combinatorio de ordenar permutaciones por inversiones. Kececioglu y Sankoff conjeturaron que para cada permutación existe un orden óptimo por inversiones que no corta tiras largas en la permutación. Probaremos esta conjetura y estudiaremos más a fondo el problema del ordenamiento por inversiones para permutaciones sin tiras de tamaño uno, llamadas solitarios. Damos un algoritmo polinómico para ordenar tales permutaciones, demostrando así que los solitarios presentan el principal obstáculo en el camino hacia un algoritmo eficiente para ordenar por inversiones. Usando este resultado, probamos la fuerte conjetura de Kecedoglu-Sankoff: para cada permutación existe un orden óptimo por inversiones que nunca aumenta el número de puntos de ruptura. Finalmente, presentamos un nuevo algoritmo para ordenar por inversiones basado en la noción de giro de una permutación. Para permutaciones con O(log n) solitarios, el algoritmo se ejecuta en tiempo polinómico y sugiere un compromiso deseado de resolución para la mapeo físico de hibridación cruzada en estudios de evolución molecular. Describimos aplicaciones de este algoritmo para analizar reorganizaciones en maíz y algas verdes, en particular encontramos un escenario de reorganización más parsimonioso para Chlamydomonas moewusii frente a Chlamydomonas reinhardtii representando el caso conocido más complicado de reorganizaciones en organelas.
Hannenhalli et al. (Sun,) estudiaron esta cuestión.