尚未登入 請由此登入
 
 
 










知識分享平台Eshare檢視資訊View
返回前一頁Back
      [檢舉]

標題Title: A Fast Method for Linear Space Pairwise Sequence Alignment
作者Authors: 李育強,Chin-Chen Chang..等
上傳單位Department: 資訊工程系
上傳時間Date: 2009-12-1
上傳者Author: 李育強
審核單位Department: 資訊工程系
審核老師Teacher: 李育強
檔案類型Categories: 論文Thesis
關鍵詞Keyword: sequence alignment, DNA, dynamic, programming, Hirschberg’s algorithm, linear, space
摘要Abstract: Pairwise sequence alignment is an important technique for finding the optimal arrangement between two sequences. A basic dynamic-programming strategy for sequence alignment needs O(mn) time and also O(mn) space. Hirschberg’s divide-and-conquer method reduces the required space to roughly 2m (m ≤ n), but it also doubles the omputing time. On the other hand, the FastLSA approach adds extra
rows and columns to generalize Hirschberg’s algorithm, reducing the number of recomputations at the cost of more memory space. In this
paper, we shall present an efficient linear space algorithm, called the NFLSA algorithm, to reduce the ratio of recalculation greater than FastLSA while using the same memory. The NFLSA algorithm is superior to Hirschberg’s algorithm and the FastLSA algorithm in our
simulations.

檔案名稱
FileName
檔案大小
Size
檔案格式
Format
瀏覽次數
Browses
下載次數
Downloads
2009_12_50c8fd01.pdf 135Kb pdf 704 306
文件中檔案:
 

開啟檔案Download
 
 
返回前一頁