Feature #3: Locate Protein
Implementing the "Locate Protein" feature for our "Computational Biology" project.
We'll cover the following...
Description
Experiments have shown that a certain protein provides immunity against a specific virus. Unfortunately, the presence of the protein can’t be determined based on an exact match. Instead, we only know that like any other protein, this one has really long palindromic strings of nucleotides. To detect this protein, we need to first find the longest palindromic portion in an unknown sample.
We’ll be provided with a DNA generated protein sequence in the form of a string. Our task will be to locate and isolate the portion that has the nucleotides lined up as the longest palindrome to identify the correct protein.
Solution
A palindrome is a string that reads the same backwards as forwards. For example, str = abba is a palindrome, but str' = abcd is not. Although there can be multiple palindromes in the input string, we have to find the longest one. There are two ways we can check if a string is a palindrome:
-
Start two pointers from each end of the string. Move towards the center while checking that the element at each pointer is the same.
-
Start two pointers from the center of the string. One ...