Dynamic Programming

Nalbantoglu Ö. U.

MULTIPLE SEQUENCE ALIGNMENT METHODS, cilt.1079, ss.3-27, 2014 (SCI-Expanded, Scopus) identifier identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 1079
  • Basım Tarihi: 2014
  • Doi Numarası: 10.1007/978-1-62703-646-7_1
  • Dergi Adı: MULTIPLE SEQUENCE ALIGNMENT METHODS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.3-27
  • Anahtar Kelimeler: Dynamic programming, Needleman-Wunsch algorithm, Smith-Waterman algorithm, Affine gap penalties, Hirschberg's algorithm, Banded dynamic programming, Bounded dynamic programming, Seeding
  • Dokuz Eylül Üniversitesi Adresli: Evet

Özet

Independent scoring of the aligned sections to determine the quality of biological sequence alignments enables recursive definitions of the overall alignment score. This property is not only biologically meaningful but it also provides the opportunity to find the optimal alignments using dynamic programming-based algorithms. Dynamic programming is an efficient problem solving technique for a class of problems that can be solved by dividing into overlapping subproblems. Pairwise sequence alignment techniques such as Needleman-Wunsch and Smith-Waterman algorithms are applications of dynamic programming on pairwise sequence alignment problems. These algorithms offer polynomial time and space solutions. In this chapter, we introduce the basic dynamic programming solutions for global, semi-global, and local alignment problems. Algorithmic improvements offering quadratic-time and linear-space programs and approximate solutions with space-reduction and seeding heuristics are discussed. We finally introduce the application of these techniques on multiple sequence alignment briefly.