The multiple longest common subsequence (MLCS) problem, related to the identification of sequence similarity, is an important problem in many fields. As an NP-hard problem, its exact algorithms have difficulty in handling large-scale data and time- and space-efficient algorithms are required in real-world applications. To deal with time constraints, anytime algorithms have been proposed to generate good solutions with a reasonable time. However, there exists little work on space-efficient MLCS algorithms. In this paper, we formulate the MLCS problem into a graph search problem and present two space-efficient anytime MLCS. Computational complexity theory is the study of resource bounded computations. What are the problems that can or cannot be solved by a given model of computation, using limited amount of resources? Time, space, non-determinism and randomness are some of the common resources that we usually consider. Complexity theory has a wide range of applications in computer science and elsewhere, particularly in cryptography (designing efficient protocols that can withstand adversaries), algorithms (designing efficient algorithms), machine learning (studying the hardness of a learning algorithm), mathematics (factoring integers), physics (quantum computation), economics (finding Nash equilibria), etc. Despite several decades of research in this area, some of the most fundamental questions still remain unsolved. In this dissertation, we investigate and make progress on some questions related to space bounded computations