Cited By
View all- Wang XLiu JXu YZhang J(2015)A Survey of Multiple Sequence Alignment TechniquesIntelligent Computing Theories and Methodologies10.1007/978-3-319-22180-9_52(529-538)Online publication date: 11-Aug-2015
Efficient Parallel Implementations of Multiple Sequence Alignment using BSP/CGM Model
Authors: 
Jucele F. A. Vasconcellos, Christiane Nishibe, Nalvo F. Almeida, Edson N. CáceresAuthors Info & Claims
Pages 103 - 110
Abstract
Multiple sequence alignment is a fundamental tool in bioinformatics, widely used for predicting protein structure and function, reconstructing phylogeny and several other biological sequence analyses. Because it is a NP-hard problem, several studies have been conducted to propose efficient methods to solve it. Based on the well-known approximate algorithm proposed by Gusfield [8], we present two parallel solutions for this problem using the BSP/CGM model, with MPI and CUDA implementations. The results show that the use of parallel processing allows the manipulation of more and larger sequences.
References
[1]
C. Alves, E. Cáceres, F. Dehne, and S. Song. A Parallel Wavefront Algorithm for Efficient Biological Sequence Comparison. In International Conference on Computational Science and its Applications (ICCSA 2003), volume 2668, pages 249--258. Springer-Verlag Berlin Heidelberg, 2003.
[2]
J. Blazewicz, W. Frohmberg, M. Kierzynka, and P. Wojciechowski. G-MSA --- A GPU-based, fast and accurate algorithm for multiple sequence alignment. J. Parallel Distrib. Comput., 73:32--41, 2013.
[3]
H. Carrillo and D. Lipman. The multiple sequence alignment problem in biology. SIAM J. Appl. Math., 48(5):1073--1082, Oct. 1988.
[4]
F. Dehne, A. Fabri, and A. Rau-Chaplin. Scalable Parallel Computational Geometry for Coarse Grained Multicomputers. International Journal on Computational Geometry, 6:298--307, 1996.
[5]
X. Deng, E. Li, J. Shan, and W. Chen. Parallel implementation and performance characterization of muscle. In Parallel and Distributed Processing Symposium, 2006. IPDPS 2006. 20th International, 2006.
[6]
R. Edgar. MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Research, 32(5):1792--1797, Mar. 2004.
[7]
O. Gotoh. Consistency of Optimal Sequence Alignments. Bulletin of Mathematical Biology, 52(4):509--525, 1990.
[8]
D. Gusfield. Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds. Bulletin of Mathematical Biology, 55(1):141--154, 1993.
[9]
D. Gusfield. Algorithms on Strings, Trees and Sequences, chapter 14. Cambridge University Press, 1997.
[10]
S. Jung, J. Na, C. Choi, F. Nazareno, I. Jung, W. Cho, M. Tang, and S. Jun. A private cloud system for web-based high-performance multiple sequence alignment services. In Intelligent Systems Modelling Simulation (ISMS), 2013 4th International Conference on, pages 143--147, 2013.
[11]
J. Kececioglu. The maximum weight trace problem in multiple sequence alignments. In Combinatorial Pattern Matching, Lecture Notes in Computer Science, volume 684, pages 106--119. Springer Berlin Heidelberg, 1993.
[12]
M. Kim. Conditional Alignment Random Fields for Multiple Motion Sequence Alignment. IEEE Transactions on Pattern Analysis and Machine Intelligence, May 2013. to be published.
[13]
D. Kirk and W. Hwu. Programming Massively Parallel Processors. Morgan Kaufmann, Waltham, MA, second edition, 2013.
[14]
J. Kleinjung, N. Douglas, and J. Heringa. Parallelized multiple alignment. Bioinformatics, 18(9):1270--1271, 2002.
[15]
A. Lukashin, J. Engelbrecht, and S. Brunak. Multiple alignment using simulated annealing: branch point definition in human mRNA splicing. Nucleic Acids Research, 20(10):2511--2516, 1992.
[16]
L. M. O. Matos, D. Pratas, and A. J. Pinho. A Compression Model for DNA Multiple Sequence Alignment Blocks. IEEE Transactions on Information Theory, 59(5):3189--3198, May 2013.
[17]
D. Mikhailov, H. Cofer, and R. Gomperts. Performance optimization of clustalw: parallel clustalw, ht clustal, and multiclustal. White Paper, 2001.
[18]
D. Mount. Bioinformatics: Sequence and Genome Analysis, chapter 4. Cold Spring Harbor Laboratory Press, New York, second edition, 2004.
[19]
F. Naznin, R. Sarker, and D. Essam. Progressive Alignment Method Using Genetic Algorithm for Multiple Sequence Alignment. IEEE Transactions on Evolutionary Computation, 16(5):615--631, Oct. 2012.
[20]
S. B. Needleman and C. D. Wunsch. A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins. Journal of Molecular Biology, 48(3):443--453, 1970.
[21]
C. Notredame. Recent progresses in multiple sequence alignment: a survey. Pharmacogenomics, 3:131--144, Jan. 2002.
[22]
C. Notredame and D. G. Higgins. SAGA: sequence alignment by genetic algorithm. Nucleic Acids Research, 24(8):1515--1524, 1996.
[23]
C. Notredame, D. G. Higgins, and J. Heringa1. T-Coffee: A Novel Method for Fast and Accurate Multiple Sequence Alignment. J. Mol. Biol., 302:205--217, Sept. 2000.
[24]
P. Pacheco. An Introduction to Parallel Programming. Morgan Kaufmann, Burlington, MA, 2011.
[25]
D. Patterson. The trouble with multicore. IEEE Spectrum, 47(7):28--32, July 2010.
[26]
E. Sandes and A. Melo. Retrieving Smith-Waterman Alignments with Optimizations for Megabase Biological Sequences using GPU. IEEE Transactions on Parallel and Distributed Systems, 24(5):1009--1021, May 2013.
[27]
J. Setubal and J. Meidanis. Introduction to Computational Molecular Biology. PWS Publishing, Boston, MA, Jan. 1997.
[28]
J. D. Thompson, D. G. Higgins, and T. J. Gibson. CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Research, 22(22):4673--4680, Nov. 1994.
[29]
O. Trelles. On the parallelisation of bioinformatics applications. Brief. Bioinform., 2:181--194, 2001.
[30]
L. G. Valiant. A Bridging Model for Parallel Computation. Commun. ACM, 33(8):103--111, 1990.
[31]
L. G. Valiant. A bridging model for multi-core computing. Journal of Computer and System Sciences, 77(1):154--166, Jan. 2011.
[32]
L. Vinh, T. Lang, N. Du, and V. Chau. Multiple Sequence Alignment on the Grid Computing using Cache Technique. International Journal of Computer Science and Telecommunications, 3(7):46--51, 2012.
[33]
L. Wang and T. Jiang. On the complexity of multiple sequence alignment. Journal of Computational Biology, 1(4):337--348, 1994.
Index Terms
- Efficient Parallel Implementations of Multiple Sequence Alignment using BSP/CGM Model
Recommendations
Efficient Parallel Implementations of Multiple Sequence Alignment using BSP/CGM Model
PMAM'14: Proceedings of Programming Models and Applications on Multicores and ManycoresMultiple sequence alignment is a fundamental tool in bioinformatics, widely used for predicting protein structure and function, reconstructing phylogeny and several other biological sequence analyses. Because it is a NP-hard problem, several studies ...
Splice-Aware Multiple Sequence Alignment of Protein Isoforms
BCB '18: Proceedings of the 2018 ACM International Conference on Bioinformatics, Computational Biology, and Health InformaticsMultiple sequence alignment (MSA) is a classic problem in computational genomics. In typical use, MSA software is expected to align a collection of homologous genes, such as orthologs from multiple species or duplication-induced paralogs within a ...
Parallel H4MSA for Multiple Sequence Alignment
TRUSTCOM-BIGDATASE-ISPA '15: Proceedings of the 2015 IEEE Trustcom/BigDataSE/ISPA - Volume 03Multiple Sequence Alignment (MSA) is the process of aligning three or more nucleotides/amino-acids sequences at the same time. It is an NP-complete optimization problem where the time complexity of finding an optimal alignment raises exponentially when ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 2014
156 pages
Copyright © 2014 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 February 2014
Check for updates
Author Tags
Qualifiers
- Tutorial
- Research
- Refereed limited
Conference
PPoPP '14
Sponsor:
PPoPP '14: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
February 15 - 19, 2014
FL, Orlando, USA
Acceptance Rates
Overall Acceptance Rate 53 of 97 submissions, 55%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 213Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Dec 2024
Other Metrics
Citations
Cited By
View all- Wang XLiu JXu YZhang J(2015)A Survey of Multiple Sequence Alignment TechniquesIntelligent Computing Theories and Methodologies10.1007/978-3-319-22180-9_52(529-538)Online publication date: 11-Aug-2015
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in