Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Moving Object Detection and Tracking Based on Three-Frame Difference and Background Subtraction with Laplace Filter Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Parallel Cache Efficient Algorithm and Implementation of Needleman-Wunsch Global Sequence Alignment

Authors : Marek Pałkowski, Krzysztof Siedlecki, Włodzimierz Bielecki

Published in: Artificial Intelligence and Soft Computing

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

An approach allowing us to improve the locality of a parallel Needleman-Wunsch (NW) global sequence alignment algorithm is proposed. The original NW algorithm works with an arbitrary gap penalty function and examines all possible gap lengths. To compute the score of an element of an NW array, cells gap symbols are looked back over entire row and column as well as one adjacent cell. We modified the NW algorithm so to read cells only with the row-major order by means of forming a copy of the transposed scoring array. The loop skewing technique is used to generate parallel code. A formal parallel NW algorithm is presented. Experimental results demonstrate super-linear speed-up factor of the accelerated code due to considerable increasing code locality on a studied modern multi-core platform.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Features Selection for the Most Accurate SVM Gender Classifier Based on Geometrical Features
next chapter Using Fuzzy Numbers for Modeling Series of Medical Measurements in a Diagnosis Support Based on the Dempster-Shafer Theory
Footnotes
1
To depict two time lines with large disparities, we used a logarithmic time axis.
 
Literature
1.
de Almeida, T.J.B.M., Roma, N.F.V.: A parallel programming framework for multi-core DNA sequence alignment. In: International Conference on Complex, Intelligent and Software Intensive Systems, pp. 907–912, February 2010
2.
Altschul, S.F., Gish, W., Miller, W., Myers, E., Lipman, D.: A basic local alignment search tool. J. Mol. Biol. 215, 403–410 (1990)CrossRef
3.
Bielecki, W., Palkowski, M.: Perfectly nested loop tiling transformations based on the transitive closure of the program dependence graph. Soft Comput. Comput. Inf. Sci. 342, 309–320 (2015)
4.
Bondhugula, U., Hartono, A., Ramanujam, J., Sadayappan, P.: A practical automatic polyhedral parallelizer and locality optimizer. SIGPLAN Not. 43(6), 101–113 (2008)CrossRef
5.
Chang, D.J., Kimmer, C., Ouyang, M.: Accelerating the Nussinov RNA folding algorithm with CUDA/GPU. In: 10th IEEE International Symposium on Signal Processing and Information Technology, pp. 120–125, December 2010
6.
7.
Needleman, S.B., Wunsch, C.D.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 48(3), 443–453 (1970)CrossRef
8.
Padua, D.A. (ed.): Encyclopedia of Parallel Computing. Springer, New York (2011)MATH
9.
Palkowski, M., Klimek, T., Bielecki, W.: TRACO: an automatic loop nest parallelizer for numerical applications. In: Federated Conference on Computer Science and Information Systems, FedCSIS 2015, Lódz, Poland, 13–16 September 2015, pp. 681–686 (2015). https://​doi.​org/​10.​15439/​2015F34
10.
Pearson, W.R., Lipman, D.J.: Rapid and sensitive protein simlarity searches. Science 227, 1435–1441 (1985)CrossRef
11.
Smith, T., Waterman, M.: Identification of common molecular subsequences. J. Mol. Biol. 147(1), 195–197 (1981)CrossRef
12.
Wolfe, M.: Loops skewing: the wavefront method revisited. Int. J. Parallel Prog. 15(4), 279–293 (1986)CrossRef
13.
14.
Zhao, C., Sahni, S.: Cache and energy efficient alignment of very long sequences. In: IEEE 5th International Conference on Computational Advances in Bio and Medical Sciences (ICCABS), pp. 1–6 (2015)
15.
Zhao, C., Sahni, S.: Cache and energy efficient algorithms for Nussinov’s RNA folding. BMC Bioinform. 18(15), 518 (2017)CrossRef
Metadata
Title
Parallel Cache Efficient Algorithm and Implementation of Needleman-Wunsch Global Sequence Alignment
Authors
Marek Pałkowski
Krzysztof Siedlecki
Włodzimierz Bielecki
Copyright Year
2018
Book
Artificial Intelligence and Soft Computing

Print ISBN: 978-3-319-91261-5

Electronic ISBN: 978-3-319-91262-2

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-91262-2_19

Premium Partner

    Image Credits