Combing Through the Haystack

Finding the same interval of DNA in the genomes of two different organisms (often taken from different species) is highly suggestive that the interval has the same function in both organisms.

We define a motif as such a commonly shared interval of DNA. A common task in molecular biology is to search an organism’s genome for a known motif.

The situation is complicated by the fact that genomes are riddled with intervals of DNA that occur multiple times (possibly with slight modifications), called repeats. These repeats occur far more often than would be dictated by random chance, indicating that genomes are anything but random and in fact illustrate that the language of DNA must be very powerful (compare with the frequent reuse of common words in any human language).

The most common repeat in humans is the Alu repeat, which is approximately 300 bp long and recurs around a million times throughout every human genome. However, Alu has not been found to serve a positive purpose, and appears in fact to be parasitic: when a new Alu repeat is inserted into a genome, it frequently causes genetic disorders.

#### Problem

Given two strings* s* and *t*, *t* is a substring of *s* if *t* is contained as a contiguous collection of symbols in *s* (as a result, *t* must be no longer than *s*).

The position of a symbol in a string is the total number of symbols found to its left, including itself (e.g., the positions of all occurrences of ‘U’ in “AUGCUUCAGAAAGGUCUUACG” are 2, 5, 6, 15, 17, and 18). The symbol at position *i* of *s* is denoted by *s*[*i*].

A substring of *s* can be represented as *s*[*j*:*k*], where *j* and *k* represent the starting and ending positions of the substring in *s*; for example, if *s* = “AUGCUUCAGAAAGGUCUUACG”, then *s*[2:5] = “UGCU”.

The location of a substring *s*[*j*:*k*] is its beginning position* j*; note that *t* will have multiple locations in *s* if it occurs more than once as a substring of *s*.

##### Given

Two DNA strings* **s* and *t* (each of length at most 1 kbp).

##### Return

All locations of *t* as a substring of *s*.

#### Solution

Let’s define a function that would find out the locations of substrings:

```
def substring_loc(s, t):
global result
result = []
t_len = len(t)
s_len = len(s)
for i in range(0, s_len - t_len + 1):
if s[i:i+t_len] == t:
result.append(i+1)
return result
```

Then, read the dataset:

```
with open("rosalind_subs.txt","r") as motif:
motiff = str()
for line in motif:
motiff = motiff + line
list = motiff.split("\n")
motiff_1 = list[0]
motiff_2 = list[1]
```

And finally, run the function to find the locations of substrings:

```
substring_loc(motiff_1,motiff_2)
for i in range(0, len(result)):
print(result[i], end=" ")
```

###### Important note:

This problem is taken from rosalind.info. Please visit ROSALIND to find out more about Bioinformatics problems. You may also clink onto links for the definitions of each terminology.