DNA Alignment Algorithm

Before starting coding, we need to think about "Algorithm". 

"Algorithms are very important in computer Science. The best chosen algorithm makes sure computer will do the given task at best possible manner. In cases where efficiency matter a proper algorithm is really vital to be used. An algorithm is important in optimizing a computer program according to the available resources. " (https://www.linkedin.com/pulse/importance-algorithm-its-types-shibaji-debnath)

 

It is hard to think the alignment algorithm myself, so I searched on Google. 

There was a very powerful algorithm. Scoring the alignment and showing the best scored alignment results.

This argorithm is called "Needleman-Wunsch algorithm". If you want to know detail, follow the links below.

https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm (Wikipedia)

http://web.skhu.ac.kr/~mckim1/Lecture/DS/dna/class13/class13_04.html 
Video Lecture : https://www.youtube.com/watch?v=-0gG_rOhcT8

 

Let's start with our homework, Align these 3 DNA sequences

'AAGAATAGTATTTCGCTTTTTTATA';
'AGAAATAGTATTTCGGTTAATTATA';
'AGACATACTAATTCGGTCCATTATA';

(1) Start with 5'end base of sequences. 

(2) Compare it with base of one other sequence whether they are same or not. 

(3) If they are same, "Score"+1. If they are different, "Score"-1. Do this work until the 3'end base.

(4) Repeat (2) and (3) with putting gaps. Whenever putting gaps, "Score"-2,

(5) Find the case with maximum score. That sequences are best alignment.

 

Perl code was available on google (https://www.perlmonks.org/?node_id=819506)

But it was not work because of some errors. I just fixed some parts of it. 
Code for alignment

Results