Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Longest Common Subsequence
Search Strategy
Subscribe
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,ChiaTung Lee
Edit
Title of Thesis:Application of the A* Algorithm to solve the Longest Common Subsequence from Fragments Problem
BibTex

RIS

RefWorks
Download
Y. M. Pan
,
ChiaTung Lee
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
References
(2)
Approximation Algorithms for Multiple Sequence Alignment
(
Citations: 48
)
Vineet Bafna
,
Eugene L. Lawler
,
Pavel A. Pevzner
Conference:
Combinatorial Pattern Matching  CPM
, pp. 4353, 1994
String Edits and Macromolecules: the Theory and Practice of Sequence Comparison
(
Citations: 5
)
David Sanko
,
Joseph B. Kruskal
Published in 1999.