東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Walking Tree methods for biological ...

Hsu, Tai-Ching.

FindBook

Google Book

Amazon

博客來

Walking Tree methods for biological string matching.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Walking Tree methods for biological string matching./
作者:	Hsu, Tai-Ching.
面頁冊數:	119 p.
附註:	Source: Dissertation Abstracts International, Volume: 64-10, Section: B, page: 5035.
Contained By:	Dissertation Abstracts International64-10B.
標題:	Computer Science. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3107729

Walking Tree methods for biological string matching.
Hsu, Tai-Ching.

Walking Tree methods for biological string matching. - 119 p.

Source: Dissertation Abstracts International, Volume: 64-10, Section: B, page: 5035.

Thesis (Ph.D.)--Oregon State University, 2004.

Approximate string matching is commonly used to align genetic sequences (DNA or RNA) to determine their shared characteristics. In contrast with the standard dynamic programming methods which use local edit distance models, the Walking Tree heuristic method was created to handle non-local changes, e.g., translocations, inversions, and duplications, altogether and simultaneously. The Walking Tree Method approximately maximizes the global alignment scores of matched translocations and inversions and minimizes gap penalties.Subjects--Topical Terms:

626642
Computer Science.

Walking Tree methods for biological string matching.
LDR:02587nmm 2200289 4500 001 1861399
005 20041111121755.5
008 130614s2004 eng d
035 $a (UnM)AAI3107729
035 $a AAI3107729
040 $a UnM $c UnM
100 1 $a Hsu, Tai-Ching. $3 1949000
245 1 0 $a Walking Tree methods for biological string matching.
300 $a 119 p.
500 $a Source: Dissertation Abstracts International, Volume: 64-10, Section: B, page: 5035.
500 $a Adviser: Paul Cull.
502 $a Thesis (Ph.D.)--Oregon State University, 2004.
520 $a Approximate string matching is commonly used to align genetic sequences (DNA or RNA) to determine their shared characteristics. In contrast with the standard dynamic programming methods which use local edit distance models, the Walking Tree heuristic method was created to handle non-local changes, e.g., translocations, inversions, and duplications, altogether and simultaneously. The Walking Tree Method approximately maximizes the global alignment scores of matched translocations and inversions and minimizes gap penalties.
520 $a It is heuristic because some special cases of string alignment problems have been shown to be NP-complete, e.g., determining the minimum number of flips needed to sort a sequence. We demonstrated that it produces reasonable alignments by (1) aligning a rearranged sequence with its original, (2) using alignment scores to construct distance trees of several families of organisms to compare with existing phylogenetic trees, and (3) aligning real biological sequences or whole genomes to compare with biologically annotated regions.
520 $a To construct the alignment, the original version runs in &THgr;(|P| * |T| * log |P|) sequential runtime, where P and T are the pattern string and the text string, respectively. The runtime was later improved to &THgr;(|P| * |T|) using snapshots of the tree. We call this version the "Improved Walking Tree Method". We used the "Four Russians" technique to improve it further to sub-quadratic, i.e., &THgr;(|P| * |T|/log|P|). We call this version the "Fast Walking Tree Method". The alignment of 8 million base pairs can be done in a week using a cluster of 65 Pentium II processors. Its sequential runtime can probably be improved further to &THgr;(|P| * |T|/(log,|P|)2).
590 $a School code: 0172.
650 4 $a Computer Science. $3 626642
650 4 $a Biology, Genetics. $3 1017730
690 $a 0984
690 $a 0369
710 2 0 $a Oregon State University. $3 625720
773 0 $t Dissertation Abstracts International $g 64-10B.
790 1 0 $a Cull, Paul, $e advisor
790 $a 0172
791 $a Ph.D.
792 $a 2004
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3107729