An approximation to the Longest Common Subsequence for Multiple Sequences problem using Shannon’s Entropy

Abstract

The Longest Common Subsequence for Multiples Sequences problem (LCSM), has been studied for more than 40 years, mainly motivated by its multiple applications in Bioinformatics. In this article we present a heuristic algorithm that estimates one or more solutions to the LCSM problem, using the Shannon’s Entropy as a measure of information in order to determine alignments with the greatest number of matches.

Keywords

• heuristic algorithm
• subsequence
• common subsequence
• alignment
• entropy
• simulation