Fast semi-local alignment for DNA sequence database search

Yong-Sheng Chen; Yi Ping Hung; Chiou Shann Fuh

doi:10.1109/ICPR.2002.1048211

Fast semi-local alignment for DNA sequence database search

Yong-Sheng Chen^*, Yi Ping Hung, Chiou Shann Fuh

^*Corresponding author for this work

Institute of Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

Given a query DNA sequence, our goal is to find in the DNA sequence database all the sequence segments that are similar to the query. In this paper we present a string-to-signal transform technique that can transform a DNA sequence into a four-channel signal. Without considering gaps, the edit distance between two DNA sequences can be calculated as the sum of absolute difference (SAD) between their corresponding four-channel signals. The algorithm proposed in this paper can then be applied to speed up the process of searching for the desired sequence segments that yield small SADs. In addition to efficiency, this algorithm guarantees the optimal search. That is, all the sequence segments that are similar enough to the query can be found without any miss.

Original language	English
Pages (from-to)	1019-1022
Number of pages	4
Journal	Proceedings - International Conference on Pattern Recognition
Volume	16
Issue number	3
DOIs	https://doi.org/10.1109/ICPR.2002.1048211
State	Published - 1 Dec 2002

Access to Document

10.1109/ICPR.2002.1048211

Cite this

@article{7a373ab565b34e72905a2188288f50e2,

title = "Fast semi-local alignment for DNA sequence database search",

abstract = "Given a query DNA sequence, our goal is to find in the DNA sequence database all the sequence segments that are similar to the query. In this paper we present a string-to-signal transform technique that can transform a DNA sequence into a four-channel signal. Without considering gaps, the edit distance between two DNA sequences can be calculated as the sum of absolute difference (SAD) between their corresponding four-channel signals. The algorithm proposed in this paper can then be applied to speed up the process of searching for the desired sequence segments that yield small SADs. In addition to efficiency, this algorithm guarantees the optimal search. That is, all the sequence segments that are similar enough to the query can be found without any miss.",

author = "Yong-Sheng Chen and Hung, {Yi Ping} and Fuh, {Chiou Shann}",

year = "2002",

month = dec,

day = "1",

doi = "10.1109/ICPR.2002.1048211",

language = "English",

volume = "16",

pages = "1019--1022",

journal = "Proceedings - International Conference on Pattern Recognition",

issn = "1051-4651",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - Fast semi-local alignment for DNA sequence database search

AU - Chen, Yong-Sheng

AU - Hung, Yi Ping

AU - Fuh, Chiou Shann

PY - 2002/12/1

Y1 - 2002/12/1

N2 - Given a query DNA sequence, our goal is to find in the DNA sequence database all the sequence segments that are similar to the query. In this paper we present a string-to-signal transform technique that can transform a DNA sequence into a four-channel signal. Without considering gaps, the edit distance between two DNA sequences can be calculated as the sum of absolute difference (SAD) between their corresponding four-channel signals. The algorithm proposed in this paper can then be applied to speed up the process of searching for the desired sequence segments that yield small SADs. In addition to efficiency, this algorithm guarantees the optimal search. That is, all the sequence segments that are similar enough to the query can be found without any miss.

AB - Given a query DNA sequence, our goal is to find in the DNA sequence database all the sequence segments that are similar to the query. In this paper we present a string-to-signal transform technique that can transform a DNA sequence into a four-channel signal. Without considering gaps, the edit distance between two DNA sequences can be calculated as the sum of absolute difference (SAD) between their corresponding four-channel signals. The algorithm proposed in this paper can then be applied to speed up the process of searching for the desired sequence segments that yield small SADs. In addition to efficiency, this algorithm guarantees the optimal search. That is, all the sequence segments that are similar enough to the query can be found without any miss.

UR - http://www.scopus.com/inward/record.url?scp=33751566117&partnerID=8YFLogxK

U2 - 10.1109/ICPR.2002.1048211

DO - 10.1109/ICPR.2002.1048211

M3 - Article

AN - SCOPUS:33751566117

SN - 1051-4651

VL - 16

SP - 1019

EP - 1022

JO - Proceedings - International Conference on Pattern Recognition

JF - Proceedings - International Conference on Pattern Recognition

IS - 3

ER -

Fast semi-local alignment for DNA sequence database search

Abstract

Access to Document

Other files and links

Fingerprint

Cite this