Subsecuencia Común más Larga en Múltiples Secuencias mediante Medidas de la Información

Abstract

El problema de la Subsecuencia Común más Larga de Múltiples Secuencias (SCLM), ha sido ampliamente estudiado en Ciencias de la Computación desde hace más de 40 años, motivado principalmente por sus diversas aplicaciones en Bioinformática. Este problema consiste en calcular una subsecuencia de longitud máxima, común a un conjunto de secuencias dado. En este trabajo se propone un algoritmo heurístico capaz de aproximar una o varias soluciones al problema SCLM utilizando la entropía de Shannon como una medida de la información para determinar los alineamientos que generen las mejores aproximaciones a la solución del problema.

Abstract: The problem of the Longest Common Multiple Sequence (MLCS), has been widely studied in Computer Science for more than 40 years, mainly motivated by its diverse applications in Bioinformatics. This problem consists in calculating a subsequence of maximum length, common to a set of given sequences. In this paper we propose a heuristic algorithm able to approximate one or several solutions to the MLCS problem using the Shannon entropy as a measure of the information to determine the alignments that generate the best approximations to the solution of the problem.