Uno de los problemas fundamentales de la bioinformática es el reconocimiento computacional de los sitios de unión de ADN y ARN. Dado un conjunto de secuencias cortas de ADN o ARN de igual longitud, como sitios de unión de factores de transcripción o sitios de empalme de ARN, la tarea es aprender un patrón a partir de este conjunto que permita el reconocimiento de sitios similares en otro conjunto de secuencias de ADN o ARN. Los modelos de Markov permutados (PM) y los modelos de Markov de longitud variable permutados (PVLM) son dos modelos poderosos para esta tarea, pero el problema de encontrar un modelo PM óptimo o un modelo PVLM es NP-duro. Mientras que el problema de encontrar un modelo PM óptimo o un modelo PVLM de orden uno es equivalente al problema del viajante de comercio (TSP), el problema de encontrar un modelo PM óptimo o un modelo PVLM de orden dos es equivalente al problema del TSP cuadrático (QTSP). Existen varios algoritmos exactos para resolver el QTSP, pero no está claro si estos algoritmos son capaces de resolver instancias de QTSP resultantes de sitios de empalme de ARN de al menos 150 pares de bases en un tiempo razonable. Aquí, investigamos el rendimiento de tres algoritmos exactos para resolver el QTSP para diez conjuntos de datos de sitios aceptores de empalme y sitios donantes de empalme de cinco especies diferentes y encontramos que uno de estos algoritmos es capaz de resolver instancias de QTSP de hasta 200 pares de bases en menos de dos días.