Academic
Publications
Title of Thesis:Application of the A* Algorithm to solve the Longest Common Subsequence from Fragments Problem

Title of Thesis:Application of the A* Algorithm to solve the Longest Common Subsequence from Fragments Problem,Y. M. Pan,Chia-Tung Lee

Title of Thesis:Application of the A* Algorithm to solve the Longest Common Subsequence from Fragments Problem  
BibTex | RIS | RefWorks Download
Finding longest common subsequence (LCS) is a common problem in Biology informatics. The problem is defined as follows: Given two strings X=x1x2…xm and Y=y1y2…yn, find a common subsequence L=l1l2…lp of X and Y such that p is maximized. In this thesis, we discuss a variation of the LCS problem - LCS from fragments problem defined as follows: Given two strings X and Y and a set M of fragments which are matching substrings of X and Y, find a LCS from M. A new method using a tree searching strategy, A* algorithm, is proposed in this study for the LCS from fragments problem. The method can help us to filter out some fragments which wouldn't appear in solutions, and efficiently find a solution. However, in worst cases, all fragments are needed to be computed in the solving process.
Cumulative Annual