ECAI 2004 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

An Effective Branch-and-Bound Algorithm to Solve the k-Longest Common Subsequence Problem

Gaofeng Huang, Andrew Lim

In this paper, we study the Longest Common Subsequence problem of multiple sequences. Because the problem is NP-hard, we devise an effective Branch-and-Bound algorithm to solve the problem. Results of extensive computational experiments show our method to be effective not only on randomly generated benchmark instances, but also on real-world protein sequence instances.

Keywords: Search, Branch-and-Bound, Bioinformatics, real-world protein sequence

Citation: Gaofeng Huang, Andrew Lim: An Effective Branch-and-Bound Algorithm to Solve the k-Longest Common Subsequence Problem. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.191-195.


[prev] [tofc] [next]

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).