Efficient Algorithms for Local Alignment Search

被引：0
作者：
S. Rajasekaran
H. Nick
P.M. Pardalos
S. Sahni
G. Shaw
机构：
[1] University of Florida,Department of Computer and Information Science and Engineering
[2] University of Florida,Department of Neuroscience
[3] University of Florida,Department of Industrial Systems Engineering
来源：
Journal of Combinatorial Optimization | 2001年 / 5卷
关键词：
local alignment research; BLAST; biological sequences; DNA sequences; protein sequences; parallel computing;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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
页数：7
相关论文
共 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] SWORD-a highly efficient protein database search
    Vaser, Robert
    Pavlovic, Dario
    Sikic, Mile
    BIOINFORMATICS, 2016, 32 (17) : 680 - 684
  • [36] Efficient distributed breadth-first search algorithm
    Makki, SAM
    COMPUTER COMMUNICATIONS, 1996, 19 (08) : 628 - 636
  • [37] 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
  • [38] 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
  • [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
12345