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)

 

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

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

Because they have same length(25b), the algorithm is simple,

(1) Start with 5'end base of first sequence. 

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

(3) If they are same, remain the base. If they are different, put "-" instead of existing base.

(4) Repeat (2) and (3) wih third sequence.

(5) Repeat (2),(3),(4) with next base until the 3'end base.

 

I thought it could be utilized in very restrictive condition, so I wanted to make "Master Code" that could be utilized in any condition.

It is hard to think 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