Efficient algorithms for local alignment search

被引：13

作者：

Rajasekaran, S ^{[1
]}

Nick, H

Pardalos, PM

Sahni, S

Shaw, G

机构：

[1] Univ Florida, Dept Comp & Informat Sci & Engn, Gainesville, FL 32611 USA

[2] Univ Florida, Dept Neurosci, Gainesville, FL 32611 USA

[3] Univ Florida, Dept Ind Syst Engn, Gainesville, FL 32611 USA

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2001年 / 5卷 / 01期

关键词：

local alignment research; BLAST; biological sequences; DNA sequences; protein sequences; parallel computing;

D O I：

10.1023/A:1009893719470

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We present efficient algorithms for local alignment search in biological sequences. These algorithms identify maximal segment pairs (MSPs). Our algorithms have the potential of performing better than BLAST (Basic Local Alignment Search Tool) and also are efficiently parallelizable. We employ Fast Fourier Transforms (FFTs). Though several attempts have been made in the past to employ FFTs in sequence analysis, they fail to capture local similarities. Our algorithms employ FFTs in a novel way to identify local similarities. FFT-based techniques have the attractive feature of benefiting from ultrafast special purpose hardware available for digital signal processing.

引用

页码：117 / 124

页数：8

共 50 条

[31] Efficient parallel algorithms for planar st-graphs
Atallah, MJ
Chen, DZ
Daescu, O
ALGORITHMICA, 2003, 35 (03) : 194 - 215
[32] EFFICIENT DESIGN AND IMPLEMENTATION OF VISUAL COMPUTING ALGORITHMS ON THE GPU
Park, In Kyu
Singhal, Nitin
Lee, Man Hee
Cho, Sungdae
2009 16TH IEEE INTERNATIONAL CONFERENCE ON IMAGE PROCESSING, VOLS 1-6, 2009, : 2321 - +
[33] Blast-Parallel: The Parallelizing Implementation Of Sequence Alignment Algorithms Based On Hadoop Platform
Meng, Ming
Gao, Jing
Chen, Jun-jie
PROCEEDINGS OF THE 2013 6TH INTERNATIONAL CONFERENCE ON BIOMEDICAL ENGINEERING AND INFORMATICS (BMEI 2013), VOLS 1 AND 2, 2013, : 465 - 470
[34] Efficient breadth-first search on the Cell/BE processor
Scarpazza, Daniele Paolo
Villa, Oreste
Petrini, Fabrizio
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2008, 19 (10) : 1381 - 1395
[35] Efficient distributed breadth-first search algorithm
Makki, SAM
COMPUTER COMMUNICATIONS, 1996, 19 (08) : 628 - 636
[36] SWORD-a highly efficient protein database search
Vaser, Robert
Pavlovic, Dario
Sikic, Mile
BIOINFORMATICS, 2016, 32 (17) : 680 - 684
[37] Algebraic Bayesian Networks: Parallel Algorithms for Maintaining Local Consistency
Kharitonov, Nikita A.
Maksimov, Anatolii G.
Tulupyev, Alexander L.
PROCEEDINGS OF THE FOURTH INTERNATIONAL SCIENTIFIC CONFERENCE INTELLIGENT INFORMATION TECHNOLOGIES FOR INDUSTRY (IITI'19), 2020, 1156 : 214 - 222
[38] Comparative analysis of the quality of a global algorithm and a local algorithm for alignment of two sequences
Polyanovsky, Valery O.
Roytberg, Mikhail A.
Tumanyan, Vladimir G.
ALGORITHMS FOR MOLECULAR BIOLOGY, 2011, 6
[39] ASCII Art Generation using the Local Exhaustive Search on the GPU
Takeuchi, Yuji
Takafuji, Daisuke
Ito, Yasuaki
Nakano, Koji
2013 FIRST INTERNATIONAL SYMPOSIUM ON COMPUTING AND NETWORKING (CANDAR), 2013, : 194 - 199
[40] Collaborative Parallel Local Search for Simplified Protein Structure Prediction
Rashid, Mahmood A.
Newton, M. A. Hakim
Hoque, Md Tamjidul
Sattar, Abdul
2013 12TH IEEE INTERNATIONAL CONFERENCE ON TRUST, SECURITY AND PRIVACY IN COMPUTING AND COMMUNICATIONS (TRUSTCOM 2013), 2013, : 966 - 973

← 1 2 3 4 5 →