PROG0163 - Palindromic sequences
A DNA sequence can be represented by a string consisting only of the letters A, C, G and T. The inverse complement of a DNA sequence is obtained by reversing the order of the letters in the string, and switching each A to a T (and vice versa), and each G to a C (and vice versa). For example, the inverse complement of the DNA sequence AGCTGCT is AGCAGCT. A palindromic sequence is a DNA sequence of which the inverse complement reads exactly the same. For example, the inverse complement of the DNA sequence AATGCATT equals the original DNA sequence, and such a DNA sequence is thus an example of a palindromic sequence.
Assignment
- Write a function DNAPalindrome to which a DNA sequence must be passed as argument. This function must return the value True if the given DNA sequence is a palindromic sequence. Otherwise, the value False must be returned.
- Use the DNAPalindrome
function for writing a longestPalindrome
function. This function must be passed a DNA sequence as
argument. The function must return the longest palindromic subsequence
of the given sequence as a result. In order to find the longest
palindromic subsequence you can go through all possible subsequences of
the given DNA sequence, test whether it is a palindromic sequence, and
eventually retain the longest palindrome. To go through all possible
subsequences of a given DNA sequence, you can go through all the
possible starting positions and through all possible stop positions for
each possible starting position. That way you can find any subsequence
as the sequence between any combination of possible start and stop
positions.
Example
>>> DNAPalindrome('GAATTC') True >>> DNAPalindrome('GAAATTC') False >>> DNAPalindrome('ACCGGT') True >>> longestPalindrome('GGGCCTATTGACTTCTTATCGTAGCCGGCCTTGTTAGTAGATGAGAATCA') 'GCCGGC' >>> longestPalindrome('AGCGCCTTGCAGCCGGGGACGGTGAGTTGGTAGCGCCCCTCAGGTCACTG') 'GCGC'
Een DNA sequentie kan voorgesteld worden door een string die enkel bestaat uit de letters A, C, G en T. Het invers complement van een DNA sequentie wordt bekomen door de volgorde van de letters in de string om te keren, en daarbij elk voorkomen van een A te wijzigen in een T (en omgekeerd) en elk voorkomen van een G in een C (en omgekeerd). Zo is het invers complement van de DNA sequentie AGCTGCT bijvoorbeeld AGCAGCT. Een palindromische sequentie is een DNA sequentie die precies hetzelfde leest op de complementaire string. Zo is het invers complement van de DNA sequentie AATGCATT gelijk aan de oorspronkelijke DNA sequentie, en is deze DNA sequentie dus een voorbeeld van een palindromische sequentie.
Opgave
- Schrijf een functie DNAPalindroom waaraan een DNA sequentie als argument moet doorgegeven worden. Deze functie moet als resultaat de waarde True teruggeven indien de gegeven DNA sequentie een palindromische sequentie is. Anders moet de waarde False teruggegeven worden.
- Gebruik de functie DNAPalindroom om een functie langstePalindroom te schrijven. Aan deze functie moet een DNA sequentie als argument doorgegeven worden. De functie moet de langste palindromische deelsequentie van de gegeven sequentie als resultaat teruggeven. Om de langste palindromische deelsequentie te vinden, kan je alle mogelijke deelsequenties van de gegeven DNA sequentie overlopen, testen of het gaat om een palindromische sequentie, en uiteindelijk het langste palindroom overhouden. Om alle mogelijke deelsequenties van een gegeven DNA sequentie te doorlopen, kan je alle mogelijke startposities doorlopen en voor elke mogelijke startpositie alle mogelijke stopposities doorlopen. Op die manier vind je elke deelsequentie als de sequentie tussen elke combinatie van mogelijke start- en stopposities.
Voorbeeld
>>> DNAPalindroom('GAATTC') True >>> DNAPalindroom('GAAATTC') False >>> DNAPalindroom('ACCGGT') True >>> langstePalindroom('GGGCCTATTGACTTCTTATCGTAGCCGGCCTTGTTAGTAGATGAGAATCA') 'GCCGGC' >>> langstePalindroom('AGCGCCTTGCAGCCGGGGACGGTGAGTTGGTAGCGCCCCTCAGGTCACTG') 'GCGC'
| Added by: | Peter Dawyndt |
| Date: | 2011-08-29 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS