We have just seen how to find the longest common subsequence. Using the same principle, we can implement DNA or protein sequencing, which can be very helpful for us in solving bioinformatic problems. For alignment purpose, we will use the most popular algorithm known as the Needleman-Wunsch algorithm. It is similar to our LCS algorithm, but the scoring system is different. Here, we score a match, mismatch, and gap in a different scoring system. There are two parts of the algorithm: one to calculate the matrix with possible sequence and the second part is tracking back the actual sequence with the best possible one. The Needleman-Wunsch algorithm provides the best global alignment solution for any given ...
DNA sequencing using dynamic programming
Get PHP 7 Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
