English  |  正體中文  |  简体中文  |  Items with full text/Total items : 28611/40649
Visitors : 648377      Online Users : 61
RC Version 4.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search

Please use this identifier to cite or link to this item: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/44278

Title: Ladderlike Stepping and Interval Jumping Searching Algorithm for DNA Sequences
Authors: Tun-Wen Pai
Margaret Dah-Tsyr Chang
Jia-Han Chu
Wei-Yuan Chang
Hsiu Ling Tai
Contributors: 國立臺灣海洋大學:資訊工程學系
NTOU:Department of Computer Science and Engineering
Keywords: Stepping
Interval Jumping
Hashing Encoding
Date: 2004
Issue Date: 2017-11-21T07:15:45Z
Publisher: The Second Asia-Pacific Bioinformatics Conference (APBC2004)
Abstract: Abstract:In this study we have designed a novel algorithm for searching common segments in multiple DNA sequences. To improve efficiency in pattern searching, combination of hashing encoding, quick sorting and ladderlike stepping and/or interval jumping techniques are applied. Since multiple sequence alignment of DNA sequences from the giant genomic database is usually time consuming, we develop a three-phase methodology to search common sub-segments and reduce its time complexity for pattern matching. In the first coding phase, DNA nucleotide sequences are transformed into a numerical space set. Subsequently, the quick sort algorithms are employed in the second sorting stage to reorder the encoded data. In the last searching phase, ladderlike stepping and interval jumping rules are proposed to increase efficiencies of numerical comparison. In addition, two interval segmentation techniques, uniform partition and bitwise partition are applied prior to interval jumping procedures. The segmenting methodologies are designed according to the length of searching pattern, and the proposed ladderlike searching algorithms provide robust and improved performance. Experimental results show that the algorithms are capable of reducing time complexity from O(mLi(Li - m +1)+mLj(Lj-m+1)) to O(|Ii|+|Ij|).
URI: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/44278
Appears in Collections:[資訊工程學系] 演講及研討會

Files in This Item:

File Description SizeFormat

All items in NTOUR are protected by copyright, with all rights reserved.


著作權政策宣告: 本網站之內容為國立臺灣海洋大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,請合理使用本網站之內容,以尊重著作權人之權益。
網站維護: 海大圖資處 圖書系統組
DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback