Near-Optimal Block Alignments
スポンサーリンク
概要
- 論文の詳細を見る
The optimal alignment of two given biosequences is mathematically optimal, but it may not be a biologically optimal one. To investigate more possible alignments with biological meaning, one can relax the scoring functions to get near-optimal alignments. Though the near optimal alignments increase the possibility of finding the correct alignment, they may confuse the biologists because the size of candidates is large. In this paper, we present the filter scheme for the near-optimal alignments. An easy method for tracing the near-optimal alignments and an algorithm for filtering those alignments are proposed. The time complexity of our algorithm is O(dmn) in the worst case, where d is the maximum distance between the near-optimal alignments and the optimal alignment, and m and n are the lengths of the input sequences, respectively.
- （社）電子情報通信学会の論文
- 2008-03-01
著者
-
Tseng Kuo-tsung
Department Of Computer Science And Engineering National Sun Yat-sen University
-
YANG Chang-Biau
Department of Computer Science and Engineering, National Sun Yat-sen University
-
HUANG Kuo-Si
Department of Computer Science and Engineering, National Sun Yat-sen University
-
PENG Yung-Hsing
Department of Computer Science and Engineering, National Sun Yat-sen University
-
Huang Kuo-si
Department Of Computer Science And Engineering National Sun Yat-sen University
-
Yang Chang-biau
Department Of Computer Science And Engineering National Sun Yat-sen University
-
Peng Yung-hsing
Department Of Computer Science And Engineering National Sun Yat-sen University
関連論文
- A Fast Initialization Algorithm for Single-Hop Wireless Networks(Network)
- Near-Optimal Block Alignments
- Generalization of Sorting in Single Hop Wireless Networks(Computation and Computational Models)
- Efficient Algorithms for Finding a Tree 3-Spanner on Permutation Graphs(Algorithms)
- Efficient Algorithms for Finding a Tree 3-Spanner on Permutation Graphs