elais/Needleman-wunsch.py

## Needleman-wunsch.py
#!/usr/bin/env python
#
# Copyright 2013 Elais Jackson.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OM ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
#
import math
import cgi
import os
import string
import webapp2 as webapp
from random import sample
from urlparse import urlparse
from google.appengine.ext import db
from google.appengine.api import users
from google.appengine.ext.webapp.util import run_wsgi_app
from google.appengine.ext.webapp import template
import wsgiref.handlers
import random, re


# This class is where we create the main page and forms within the page.
class Mainpage(webapp.RequestHandler):
	def get(self):
	        self.response.out.write("""
			<html>
				<body>
					<p>
					Hello, welcome to Elais Jackson's Alignment project. Please input your sequences into the two
					boxes respectively and watch the magic happen. In the small box insert your gap penalty in the
					form of an integer and in the larger boxes insert your two sequences without any spaces.
					If you add spaces to the sequences the program will error out. Once you've added your gap penalty
					and two sequences sans spaces, click submit and your sequences will be aligned.
					</p>
					<form action="/global/" method="post">
						<div><textarea name="Gap" rows="1" cols = "5" value="-5"></textarea></div
						<div><textarea name="Sequence1" rows="10" cols = "60"></textarea></div>
						<div><textarea name="Sequence2" rows="10" cols = "60"></textarea></div>
						<div><input type="submit" value="Submit"></div>
					</form>
					<p>
					The source code can be found <a href="https://gist.github.com/UncleTaco/5066134">here</a>
					</p>
				</body>
			</html>""")

#this class is where we actually perform the algorithm, it uses the POST html method to post its output.
class NeedlemanWunsch(webapp.RequestHandler):
	def post(self):
		try:
			gap = int(self.request.get('Gap'))	# gap penalty... or bonus if you'd prefer.
			seq1 = self.request.get('Sequence1')	# first input sequence
			seq2 = self.request.get('Sequence2')	# second input sequence
			seq1 = list(''.join(seq1.split()))
			seq2 = list(''.join(seq2.split()))
			M = [[0 for j in seq2] for i in seq1]	# An initial 2d array filled with zeros
			I = range(len(list(self.request.get('Sequence1'))))	# this is pythonic way to iterate through the sequences, trust me.
			J = range(len(list(self.request.get('Sequence2'))))	# ""
			# Similarity scores based off of wikipedia example.
			similarityMatrix = \
			{'A': {'A': 10, 'G': -1, 'C': -3, 'T': -4},
	 		'G': {'A': -1, 'G':  7, 'C': -5, 'T': -3},
	 		'C': {'A': -3, 'G': -5, 'C':  9, 'T':  0},
	 		'T': {'A': -4, 'G': -3, 'C':  0, 'T':  8}}

			#Initialization of 2d array
			for i in I:
				M[i][0] = gap * i
			for j in J:
				M[0][j] = gap * j

			#Scoring
			for i in I[1:]:
				for j in J[1:]:
					Match = M[i-1][j-1] + similarityMatrix[seq1[i]][seq2[j]]
					Delete = M[i-1][j] + gap
					Insert = M[i][j-1] + gap
					M[i][j] = max(Match, Insert, Delete)

			# Traceback
			AlignmentA = ""
			AlignmentB = ""
			i = len(seq1) - 1
			j = len(seq2) - 1

			while ( i > 0 and j > 0 ):
				Score = M[i][j]
				ScoreDiagonal = M[i - 1][j - 1]
				ScoreUp = M[i][j-1]
				ScoreLeft = M[i-1][j]
				if (Score == ScoreDiagonal + similarityMatrix[seq1[i]][seq2[j]]):
					AlignmentA = seq1[i] + AlignmentA
					AlignmentB = seq2[j] + AlignmentB
					i -= 1
					j -= 1
				elif (Score == ScoreLeft + gap):
					AlignmentA = seq1[i] + AlignmentA
					AlignmentB = "-" + AlignmentB
					i -= 1
				elif (Score == ScoreUp + gap):
					AlignmentA = "-" + AlignmentA
					AlignmentB = seq2[j] + AlignmentB
					j -= 1
				else:
					print("algorithm error?")

			while (i > 0):
				AlignmentA = seq1[i] + AlignmentA
				AlignmentB = "-" + AlignmentB
				i -= 1
			while (j > 0):
				AlignmentA = "-" + AlignmentA
				AlignmentB = seq2[j] + AlignmentB
				j -= 1

			# Similarity
			lengthA = len(AlignmentA)
			lengthB = len(AlignmentB)
			sim1 = ""
			sim2 = ""
			length0 = 0
			k = 0
			total = 0
			similarity = 0.0

			if (lengthA > lengthB):
				sim1 = AlignmentA
				sim2 = AlignmentB
				length0 = lengthA

			else:
				sim1 = AlignmentB
				sim2 = AlignmentA
				length0 = lengthB

			while (k < length0):
				if (sim1[k] == sim2[k]):
					total += 1
				k += 1

			similarity = float(total) / float(length0) * 100.0

			# Here is where we pretty the output of the algorithm.
			self.response.out.write("""
			<html>
				<body>
					<p>
					Alignment A: %s
					</p>
					<p>
					Alignment B: %s
					</p>
					<p>
					Similarity is: %s
					</p>
				</body>
			</html>
			"""%(AlignmentA, AlignmentB, similarity))
		except:
			self.response.out.write("""
			<html>
				<body>
				<p>
				Oh dear... Something went wrong. Make sure that your string only contains ATCG and that
				your gap penalty is an integer (a whole number). Try again. Failing any of those things
				I'll concede it's me, not you :). Also make sure there are absolutely NO
				</p>
				</body>
			</html>
			""")


# Here we initialie the web app and tell it which web pages map to which functions that were defined above.
app = webapp.WSGIApplication([
	('/', Mainpage),
	('/global/', NeedlemanWunsch)
#	('/\d+', Redirect
	], debug = True)

# Main method.
def main():
	webbapp.run_wsgi_app(app)

if __name__=="__main__":
	main()
	#!/usr/bin/env python
	#
	# Copyright 2013 Elais Jackson.
	#
	# Licensed under the Apache License, Version 2.0 (the "License");
	# you may not use this file except in compliance with the License.
	# You may obtain a copy of the License at
	#
	# http://www.apache.org/licenses/LICENSE-2.0
	#
	# Unless required by applicable law or agreed to in writing, software
	# distributed under the License is distributed on an "AS IS" BASIS,
	# WITHOUT WARRANTIES OR CONDITIONS OM ANY KIND, either express or implied.
	# See the License for the specific language governing permissions and
	# limitations under the License.
	#
	import math
	import cgi
	import os
	import string
	import webapp2 as webapp
	from random import sample
	from urlparse import urlparse
	from google.appengine.ext import db
	from google.appengine.api import users
	from google.appengine.ext.webapp.util import run_wsgi_app
	from google.appengine.ext.webapp import template
	import wsgiref.handlers
	import random, re


	# This class is where we create the main page and forms within the page.
	class Mainpage(webapp.RequestHandler):
	def get(self):
	self.response.out.write("""
	<html>
	<body>
	<p>
	Hello, welcome to Elais Jackson's Alignment project. Please input your sequences into the two
	boxes respectively and watch the magic happen. In the small box insert your gap penalty in the
	form of an integer and in the larger boxes insert your two sequences without any spaces.
	If you add spaces to the sequences the program will error out. Once you've added your gap penalty
	and two sequences sans spaces, click submit and your sequences will be aligned.
	</p>
	<form action="/global/" method="post">
	<div><textarea name="Gap" rows="1" cols = "5" value="-5"></textarea></div
	<div><textarea name="Sequence1" rows="10" cols = "60"></textarea></div>
	<div><textarea name="Sequence2" rows="10" cols = "60"></textarea></div>
	<div><input type="submit" value="Submit"></div>
	</form>
	<p>
	The source code can be found <a href="https://gist.github.com/UncleTaco/5066134">here</a>
	</p>
	</body>
	</html>""")

	#this class is where we actually perform the algorithm, it uses the POST html method to post its output.
	class NeedlemanWunsch(webapp.RequestHandler):
	def post(self):
	try:
	gap = int(self.request.get('Gap')) # gap penalty... or bonus if you'd prefer.
	seq1 = self.request.get('Sequence1') # first input sequence
	seq2 = self.request.get('Sequence2') # second input sequence
	seq1 = list(''.join(seq1.split()))
	seq2 = list(''.join(seq2.split()))
	M = [[0 for j in seq2] for i in seq1] # An initial 2d array filled with zeros
	I = range(len(list(self.request.get('Sequence1')))) # this is pythonic way to iterate through the sequences, trust me.
	J = range(len(list(self.request.get('Sequence2')))) # ""
	# Similarity scores based off of wikipedia example.
	similarityMatrix = \
	{'A': {'A': 10, 'G': -1, 'C': -3, 'T': -4},
	'G': {'A': -1, 'G': 7, 'C': -5, 'T': -3},
	'C': {'A': -3, 'G': -5, 'C': 9, 'T': 0},
	'T': {'A': -4, 'G': -3, 'C': 0, 'T': 8}}

	#Initialization of 2d array
	for i in I:
	M[i][0] = gap * i
	for j in J:
	M[0][j] = gap * j

	#Scoring
	for i in I[1:]:
	for j in J[1:]:
	Match = M[i-1][j-1] + similarityMatrix[seq1[i]][seq2[j]]
	Delete = M[i-1][j] + gap
	Insert = M[i][j-1] + gap
	M[i][j] = max(Match, Insert, Delete)

	# Traceback
	AlignmentA = ""
	AlignmentB = ""
	i = len(seq1) - 1
	j = len(seq2) - 1

	while ( i > 0 and j > 0 ):
	Score = M[i][j]
	ScoreDiagonal = M[i - 1][j - 1]
	ScoreUp = M[i][j-1]
	ScoreLeft = M[i-1][j]
	if (Score == ScoreDiagonal + similarityMatrix[seq1[i]][seq2[j]]):
	AlignmentA = seq1[i] + AlignmentA
	AlignmentB = seq2[j] + AlignmentB
	i -= 1
	j -= 1
	elif (Score == ScoreLeft + gap):
	AlignmentA = seq1[i] + AlignmentA
	AlignmentB = "-" + AlignmentB
	i -= 1
	elif (Score == ScoreUp + gap):
	AlignmentA = "-" + AlignmentA
	AlignmentB = seq2[j] + AlignmentB
	j -= 1
	else:
	print("algorithm error?")

	while (i > 0):
	AlignmentA = seq1[i] + AlignmentA
	AlignmentB = "-" + AlignmentB
	i -= 1
	while (j > 0):
	AlignmentA = "-" + AlignmentA
	AlignmentB = seq2[j] + AlignmentB
	j -= 1

	# Similarity
	lengthA = len(AlignmentA)
	lengthB = len(AlignmentB)
	sim1 = ""
	sim2 = ""
	length0 = 0
	k = 0
	total = 0
	similarity = 0.0

	if (lengthA > lengthB):
	sim1 = AlignmentA
	sim2 = AlignmentB
	length0 = lengthA

	else:
	sim1 = AlignmentB
	sim2 = AlignmentA
	length0 = lengthB

	while (k < length0):
	if (sim1[k] == sim2[k]):
	total += 1
	k += 1

	similarity = float(total) / float(length0) * 100.0

	# Here is where we pretty the output of the algorithm.
	self.response.out.write("""
	<html>
	<body>
	<p>
	Alignment A: %s
	</p>
	<p>
	Alignment B: %s
	</p>
	<p>
	Similarity is: %s
	</p>
	</body>
	</html>
	"""%(AlignmentA, AlignmentB, similarity))
	except:
	self.response.out.write("""
	<html>
	<body>
	<p>
	Oh dear... Something went wrong. Make sure that your string only contains ATCG and that
	your gap penalty is an integer (a whole number). Try again. Failing any of those things
	I'll concede it's me, not you :). Also make sure there are absolutely NO
	</p>
	</body>
	</html>
	""")


	# Here we initialie the web app and tell it which web pages map to which functions that were defined above.
	app = webapp.WSGIApplication([
	('/', Mainpage),
	('/global/', NeedlemanWunsch)
	# ('/\d+', Redirect
	], debug = True)

	# Main method.
	def main():
	webbapp.run_wsgi_app(app)

	if __name__=="__main__":
	main()