Combing Through the Haystack

Given two strings s$s$ and t$t$, t$t$ is a substring of s$s$ if t$t$ is contained as a contiguous collection of symbols in s$s$ (as a result, t$t$ must be no longer than s$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$i$ of s$s$ is denoted by s[i]$s[i]$.

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

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

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

Return: All locations of t$t$ as a substring of s

t = "GATATATGCATATACTT"
s = "ATAT"

lengtht =len(t)
lengths =len(s)
index = []
indexplus =[]
for i in range(0,lengtht-lengths):
    if t[i:i+lengths]==s:
        index.append(i)

for j in range(0,len(index)):
    indexplus.append(str(index[j]+1))
print(" ".join(indexplus))

sㄴ

Combing Through the Haystack

Figure 1. The human chromosomes stained with a probe for Alu elements, shown in green.

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 (see Figure 1). 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.