Near-Optimal Block Alignments

Kuo-Tsung TSENG; Chang-Biau YANG; Kuo-Si HUANG; Yung-Hsing PENG

doi:10.1093/ietisy/e91-d.3.789

Near-Optimal Block Alignments

Kuo-Tsung TSENG, Chang-Biau YANG, Kuo-Si HUANG, Yung-Hsing PENG

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E91-D No.3 pp.789-795

Publication Date: 2008/03/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e91-d.3.789

Type of Manuscript: PAPER

Category: Algorithm Theory

Cite this

Copy

Kuo-Tsung TSENG, Chang-Biau YANG, Kuo-Si HUANG, Yung-Hsing PENG, "Near-Optimal Block Alignments" in IEICE TRANSACTIONS on Information, vol. E91-D, no. 3, pp. 789-795, March 2008, doi: 10.1093/ietisy/e91-d.3.789.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e91-d.3.789/_p

Copy

@ARTICLE{e91-d_3_789,
author={Kuo-Tsung TSENG, Chang-Biau YANG, Kuo-Si HUANG, Yung-Hsing PENG, },
journal={IEICE TRANSACTIONS on Information},
title={Near-Optimal Block Alignments},
year={2008},
volume={E91-D},
number={3},
pages={789-795},
abstract={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.},
keywords={},
doi={10.1093/ietisy/e91-d.3.789},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Near-Optimal Block Alignments
T2 - IEICE TRANSACTIONS on Information
SP - 789
EP - 795
AU - Kuo-Tsung TSENG
AU - Chang-Biau YANG
AU - Kuo-Si HUANG
AU - Yung-Hsing PENG
PY - 2008
DO - 10.1093/ietisy/e91-d.3.789
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E91-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2008
AB - 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.
ER -