Bioinformatics

Problem

A graph whose nodes have all been labeled can be represented by an adjacency list, in which each row of the list contains the two node labels corresponding to a unique edge.

A directed graph (or digraph) is a graph containing directed edges, each of which has an orientation. That is, a directed edge is represented by an arrow instead of a line segment; the starting and ending nodes of an edge form its tail and head, respectively. The directed edge with tail v$v$ and head w$w$ is represented by (v,w)$(v,w)$ (but not by (w,v)$(w,v)$). A directed loop is a directed edge of the form (v,v)$(v,v)$.

For a collection of strings and a positive integer k$k$, the overlap graph for the strings is a directed graph Ok${\mathrm{O}}_k$ in which each string is represented by a node, and string s$s$ is connected to string t$t$ with a directed edge when there is a length k$k$ suffix of s$s$ that matches a length k$k$ prefix of t$t$, as long as s≠t$s\ne t$; we demand s≠t$s\ne t$ to prevent directed loops in the overlap graph (although directed cycles may be present).

Given: A collection of DNA strings in FASTA format having total length at most 10 kbp.

Return: The adjacency list corresponding to O3${\mathrm{O}}_3$. You may return edges in any order.

Sample Dataset

>Rosalind_0498
AAATAAA
>Rosalind_2391
AAATTTT
>Rosalind_2323
TTTTCCC
>Rosalind_0442
AAATCCC
>Rosalind_5013
GGGTGGG

Sample Output

Rosalind_0498 Rosalind_2391
Rosalind_0498 Rosalind_0442
Rosalind_2391 Rosalind_2323

Problem explanation

문제의 조건들은 다음과 같습니다.

1.  비교 하는 대상이 앞에 올때 s, 비교 하는 대상이 뒤에 올때 t로 명명합니다. (이때 s와 t는 같을 수 없습니다.)

2. s의 전체 시퀀스의 뒤에서 k 만큼의 bp(시퀀스 한개 1bp)는 v를 의미하며 t의 전체 시퀀스의 앞에서 k 만큼의 bp를 추출한 것을 w로 판단합니다.

3.  v = w 의 조건에 만족한 영역들만 추출합니다.( w = v 일때는 포함되면 안됩니다.)

Source

f = open("D:/gs/rosalind/rosalind_grph.txt","r") 
k = 3
lines = f.readlines()
id = []
seq = []
#rosalind 에서 주는 txt 파일을 불러와서 나의 inputdata에 맞게 reform 합니다.
def reform(lines):
    for line in lines:
        if line.startswith(">"):
            a = line.replace(">", "")
            a = a.replace("\n", "")
            id.append(a)
        else:
            if len(id) > len(seq):
                line = line.replace("\n","")
                seq.append(line)
            else:
                line = line.replace("\n", "")
                seq[len(id) - 1] = seq[len(id) - 1] + line
    return id , seq
id, seq = reform(lines)

s = []
t = []

for i in range(len(id)):
    for j in range(len(seq)):

        if i != j:
            if seq[i][-k:] == seq[j][:k]:
                s.append(id[i])
                t.append(id[j])

for i in range(len(s)):
    print(s[i] + " " + t[i])

f.close()

A Brief Introduction to Graph Theory

Problem

Figure 4. A figure illustrating the propagation of Fibonacci's rabbits if they die after three months.

Recall the definition of the Fibonacci numbers from “Rabbits and Recurrence Relations”, which followed the recurrence relation Fn=Fn−1+Fn−2$F_n=F_{n-1}+F_{n-2}$ and assumed that each pair of rabbits reaches maturity in one month and produces a single pair of offspring (one male, one female) each subsequent month.

Our aim is to somehow modify this recurrence relation to achieve a dynamic programming solution in the case that all rabbits die out after a fixed number of months. See Figure 4 for a depiction of a rabbit tree in which rabbits live for three months (meaning that they reproduce only twice before dying).

Given: Positive integers n≤100$n\le 100$ and m≤20$m\le 20$.

Return: The total number of pairs of rabbits that will remain after the n$n$-th month if all rabbits live for m$m$ months.

month = 83
lifespan = 19
cycle = [0] * lifespan
cycle[0] = 1

for i in range(month-1):
    temp = 0
    for j in range(lifespan-1, 0, -1):
        temp = temp + cycle[j]
        cycle[j] = cycle[j-1]
    cycle[0] = temp

print(sum(cycle))

Wabbit Season

Figure 1. A c.1905 photo from Australia of a cart loaded to the hilt with rabbit skins.

Figure 2. Western Australia's rabbit fence is actually not the longest fence in the world as the sign claims. That honor goes to a 3,500 mile fence in southeastern Australia built to keep out dingoes. Courtesy Matt Pounsett.

Figure 3. An 1884 cartoon from the Queensland Figaro proposing how the rabbits viewed their fence.

In “Rabbits and Recurrence Relations”, we mentioned the disaster caused by introducing European rabbits into Australia. By the turn of the 20th Century, the situation was so out of control that the creatures could not be killed fast enough to slow their spread (see Figure 1).

The conclusion? Build a fence! The fence, intended to preserve the sanctity of Western Australia, was completed in 1907 after undergoing revisions to push it back as the bunnies pushed their frontier ever westward (see Figure 2). If it sounds like a crazy plan, the Australians at the time seem to have concurred, as shown by the cartoon in Figure 3.

By 1950, Australian rabbits numbered 600 million, causing the government to decide to release a virus (called myxoma) into the wild, which cut down the rabbits until they acquired resistance. In a final Hollywood twist, another experimental rabbit virus escaped in 1991, and some resistance has already been observed.

The bunnies will not be stopped, but they don't live forever, and so in this problem, our aim is to expand Fibonacci's rabbit population model to allow for mortal rabbits.

Problem

A matrix is a rectangular table of values divided into rows and columns. An m×n$m\times n$ matrix has m$m$ rows and n$n$ columns. Given a matrix A$A$, we write Ai,j$A_{i,j}$ to indicate the value found at the intersection of row i$i$ and column j$j$.

Say that we have a collection of DNA strings, all having the same length n$n$. Their profile matrix is a 4×n$4\times n$ matrix P$P$ in which P1,j$P_{1,j}$ represents the number of times that 'A' occurs in the j$j$th positionof one of the strings, P2,j$P_{2,j}$ represents the number of times that C occurs in the j$j$th position, and so on (see below).

A consensus string c$c$ is a string of length n$n$ formed from our collection by taking the most common symbol at each position; the j$j$th symbol of c$c$ therefore corresponds to the symbol having the maximum value in the j$j$-th column of the profile matrix. Of course, there may be more than one most common symbol, leading to multiple possible consensus strings.

Given: A collection of at most 10 DNA strings of equal length (at most 1 kbp) in FASTA format.

Return: A consensus string and profile matrix for the collection. (If several possible consensus strings exist, then you may return any one of them.)

f= open("D:/gs/rosalind/rosalind_cons1.txt","r")

lines  = f.readlines()
seq = []
arr1 =[]
for i in range(len(lines)):
    if i%2==1:
        seq.append(lines[i])

for i in range(len(seq)):
    arr2=[]
    for j in range(len(seq[i])):
        if seq[i][j] == '\n':
            continue
        else:
            arr2.append(seq[i][j])
    arr1.append(arr2)



A = []
C = []
G = []
T = []
Max = []

for i in range(len(arr1[i])):
    a = 0
    c = 0
    g = 0
    t = 0
    temp = []
    for j in range(len(arr1)):
        if arr1[j][i]=="A":
            a+=1
        elif arr1[j][i]=="T":
            t+=1
        elif arr1[j][i]=="G":
            g+=1
        else:
            c+=1
    A.append(a)
    C.append(c)
    G.append(g)
    T.append(t)
    temp.append(a)
    temp.append(c)
    temp.append(g)
    temp.append(t)
    Max.append(temp.index(max(temp)))

count = 0
for ma in Max:
    if ma == 0:
        Max[count] = "A"
        count+=1
    elif ma == 1:
        Max[count] = "C"
        count += 1
    elif ma == 2:
        Max[count] = "G"
        count += 1
    else:
        Max[count] = "T"
        count += 1



print("".join(Max))
A = [str (i) for i in A]
C = [str (i) for i in C]
G = [str (i) for i in G]
T = [str (i) for i in T]

print("A: "+" ".join(A))
print("C: "+" ".join(C))
print("G: "+" ".join(G))
print("T: "+" ".join(T))

Finding a Most Likely Common Ancestor