Calculating the Secrets of Life Contributions of the Mathematical Sciences to Molecular Biology (1995) / Chapter Skim
Currently Skimming:
Pages 60-64
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 60... ...
to (6, 6) correspond to the two optimal global AT TA-CG AT-TACO alignments A-TATCG and ATAT-CG The Basic Dynamic Programming Algorithm We now turn to devising an algorithm, or computational procedure, for finding the score of an optimal global alignment between sequences A and B
|
From page 61... ...
G subsection. First, observe that, in terms of the edit graph formulation, we seek the score of a maximal-score path from the vertex ~ at the upper left-hand corner of the graph GA B to the vertex 0, at the lower right-hand corner.
|
From page 62... ...
Along the left and upper boundaries of the edit graph (that is, vertices with i = 0 or j = 0, respectively) , the algorithm utilizes the recurrence, except that terms referencing nonexistent vertices are omitted (that is, in lines 3 and 5, respectively)
|
From page 63... ...
The algorithm of Figure 3.3 is a dynamic programming algorithm that utilizes the fundamental recurrence. Dynamic programming is a general computational paradigm of wide applicability (see, for example, Horowitz and Sahni, 1978~.
|
From page 64... ...
have shown this strategy to apply to most comparison aigonthms that have linear-space score-only algorithms. This refinement is very important, since space, not time, is often the limiting factor in computing optimal alignments between large sequences.
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.