String Processing

Palindromes

In this lesson the student will learn how to:

Recognize palindromes programmatically
Write a script using many previously presented techniques

By the end of this lesson the student will be able to:


	Write a script which can identify sequences
	which are complementary palindromes.

Palindromes

Palindromes are letter patterns which read the same forward as backward. Here are a few examples:


	noon		racecar			level

	radar		rotator			kayak

We can apply this idea to nucleotide sequences. Here are a few nucleotide sequences which are palindromes:


	gctaatcg		ccggttggcc		atata

	atta			atcta			cgtaaatgc

One interesting this to notice about palindromes is that some have an even number of letters (in which case each letter has a match) and some have an odd number of letters (in which case the middle letter does not have a match.


	ODD:  aga	actgagtca	atata
	EVEN: agga	actgaagtca	ataata

Even more interesting than normal palindromes sequences are complementary palindromes like these:


	gcatatgc		aaatttcccgggaaattt

	atgcatgcatgcgcatgcatgcat

In these the last half of the sequence is complementary to the first half of the sequence. (The last nucleotide is complementary to the first nucleotide, the second to the last nucleotide is complementary to the second nucleotide, and so forth.)

Recognizing Palindromes

#!/usr/bin/perl @words = ("opal", "kayak", "racecar", "shaft", "banana", "elevator", "repaper", "madam", "senile_felines", "toilet", "evilolive", "dumbmud", "petrified"); foreach $item (@words){ $match=1; #does match unless found not to @letters = split("",$item); @backwards = reverse @letters; //same as @letters only in reverse order $len = length($item); for($i=0; $i<$len/2; $i++){ if($backwards[$i] ne $letters[$i]){ $match=0; } } if($match==0){ print "NOT: $item\n"; } else{ print "PAL: $item\n"; } }

See if you can add a few examples to the array at the beginning of this script.

How can you tell if two nucleotides are complementary. Try this little "Complementary Nucleotide Quizzer."

#!/usr/bin/perl %cn=( "A" => "T", "T" => "A", "G" => "C", "C" => "G" ); srand(time); @nucs = ("A", "C", "G", "T"); $cnt = 0; $correct=0; while($cnt<10){ $item=int rand(4); print "What is the complement of $nucs[$item]? "; $user = <STDIN>; chomp $user; if($user eq $cn{$nucs[$item]} ){ print "CORRECT!\n"; $correct++; } else{ print "INCORRECT\n"; } $cnt++; } print "$correct out of 10\n";

ASSIGNMENT:

Write a script which can recognize complementary palindromes like the examples shown on this page. Write a loop (which is quit by entering 'q') which allows the user to keep entering sequences indefinately. After each entry the script reports whether or not the sequence is 1) a palindrome, 2) a complementary palindrome, 3) not a palindrome.