Greedy Reassembly Algorithm:

http://web. cse. ohio-state. edu/software/2221/web-sw1/extras/sl ides/30.String-Reassembly. pdf

Carefully review the Genome/String Reassembly slides. Then, given the following fragments, reassemble the original string by applying the greedy reassembly algorithm presented in the slides. Show in each step the two strings with the longest overlap and the resulting combination.

TATACAT

AGCTGCGTT

CACTCCAA

CAAGCTGTT

TTTCGTTATACAT

CTGCGTTA

The answer is explained below

Explanation:

The greedy reassembly algorithm is used to  assembles the reads into the correct DNA sequence.

Solution:

The first step is to see the longest prefix that is the suffix of the other string is of length 11:-

AGCTGCGTT and CTGCGTTA

After combining these two we get:

AGCTGCGTTA

Next we take is of length 8:

TTTCGTTATACAT and AGCTGCGTTA

 After combining these two we get:

AGCTGCGTTATACAT

Next we take is of length 7:

TATACAT and AGCTGCGTTATACAT

We can get :

AGCTGCGTTATACAT

Next we take is of length 7 again:

CACTCCAA and CAAGCTGTT

After combining these two we get:

CACTCCAAGCTGTT

After, this we will only be left with 2 strings:

CACTCCAAGCTGTT and AGCTGCGTTATACAT

We take the length 7 again:

The final string will be:-