Multiple Longest Common Subsequence (MLCS) problem is searching all longest common subsequences of multiple character sequences. It appears in many fields such as data mining, DNA alignment, bioinformatics, text editing and so on. With the increasing of sequence length and number of sequences, the existing dynamic programming algorithms and the dominant point based algorithms become ineffective and inefficient, especially for large-scale MLCS problems.