BNFO ASSNT created by skarthik345 - https://repl.it/@skarthik345/BNFO-ASSNT

BNFO ASSNT.py

'''
Created on Feb 7, 2018

@author: Karthik
'''

import random
def getparsimonyscore(T,root,pscore):
    S=T[3]
    L=T[1]
    R=T[2]
    P=T[0]
    l=L[root]
    r=R[root]
    p=P[root]
    if(l ==-1 and r==-1):
        return pscore
    if(S[root]!=S[l]):
            pscore = pscore+1
    if(S[root]!=S[r]):
            pscore = pscore+1
    pscore = getparsimonyscore(T,l,pscore)
    pscore = getparsimonyscore(T,r,pscore)
    return pscore

def assignsequences(T,root):
    S=T[3]
    L=T[1]
    R=T[2]
    P=T[0]
    l=L[root]
    r=R[root]
    p=P[root]
    
    #assign sequence at root
    if(l ==-1 and r==-1):
        return
    #assign to current node
    if(P[root] ==-1):
        S[root]= random.choice(list(S[root]))
    #else if parent assignment exists in current node
    elif(S[p] in S[root]):
        S[root]=S[p]
    else:
        S[root] = random.choice(list(S[root]))
    #assign to left child
    #assign to right child
    assignsequences(T,l)
    assignsequences(T,r)    

def assignsets(T,root):
    S=T[3]
    L=T[1]
    R=T[2]
    P=T[0]
    if(L[root] != -1):
        assignsets(T,L[root])
    if(R[root] != -1):
        assignsets(T,R[root])
    l=L[root]
    r=R[root]
    if(l != -1 and r != -1):
        intersection = set(S[l]).intersection(set(S[r]))
        union = set(S[l]).union(set(S[r]))
        if(len(intersection) != 0):
            S[root] = intersection
        else:
            S[root] = union
    

def smallparsimony(T):
    S=T[3]
    L=T[1]
    R=T[2]
    P=T[0]
    score = 0
    root = -1
    for i in range(0, len(P), 1):
        if(P[i] == -1):
            root = i
    if(root == -1):
            print("No root!\n")
            exit()
    nleaves = int((len(P)+1)/2)
    nnodes = len(P)
    for column in range(0, len(S[0])):
        w=[]
        for i in range(0, nleaves):
            w.append(S[i][column])
        for i in range(nleaves, nnodes):
            w.append('')
        print(w)
        T = [P,L,R,w]
        assignsets(T,root)
        assignsequences(T,root)
        print(w)
        score = getparsimonyscore(T, root, score)
        for i in range(nleaves,nnodes):
            S[i] += w[i]
    return score

P = [4,4,5,5,6,6,-1]
L = [-1,-1,-1,-1,0,2,4]
R = [-1,-1,-1,-1,1,3,5]
##S= ['A','G','T','C','','','']
##S= ['A','A','C','T','','','']
S= ['AA','AA','CC','AT','','','']

T = [P,L,R,S]

##P = [8,7,6,6,9,9,7,8,10,10,-1]
##L = [-1,-1,-1,-1,-1,-1,2,1,0,4,8]
##R = [-1,-1,-1,-1,-1,-1,3,6,7,5,9]
##S = ['A','A','C','G','C','A','','','','','']

print(S)
print(smallparsimony(T))
print(S)