GreedyMotif.py

__author__ = 'Cullin'
import HammingDistance
import sys
import time
import random
random.seed()

from itertools import groupby as g

def most_common_oneliner(L):
    return max(g(sorted(L)), key=lambda(x, v):(len(list(v)),-L.index(x)))[0]

def timing(f):
    def wrap(*args):
        time1 = time.time()
        ret = f(*args)
        time2 = time.time()
        print '%s function took %0.3f ms' % (f.func_name, (time2-time1)*1000.0),args
        return ret
    return wrap


def find_most_probable_profile_kmer(text,k,profile):
    max_prob = 0
    ret_kmer = ''
    if type(profile) is dict:
        profile_dict = profile
    else:
        profile_dict = dict()
        profile_rows = ['A','C','G','T']
        for i,base in enumerate(profile_rows):
            profile_dict[base] = profile[i]

    for i in range(0,len(text) - k + 1):
        curr_prob = 1
        word = text[i:i+k]
        for i,base in enumerate(word):
            curr_prob *= profile_dict[base][i]
        if curr_prob > max_prob:
            max_prob = curr_prob
            ret_kmer = word

    return ret_kmer

def weighted_choice(choices):
    """

    :param choices: dictionary
    :return:
    """
    total = sum(w for c, w in choices.items())
    r = random.uniform(0, total)
    upto = 0
    for c, w in choices.items():
        if upto + w > r:
           return c
        upto += w
    assert False, "Shouldn't get here"

def get_weighted_random_profile_kmer(text,k,profile):
    kmer_probs = dict()

    for i in range(0,len(text) - k + 1):
        curr_prob = 1
        word = text[i:i+k]
        for i,base in enumerate(word):
            curr_prob *= profile[base][i]

        kmer_probs[word] = curr_prob

    return weighted_choice(kmer_probs)

def create_profile_matrix(motifs):
    the_matrix = {'A':[],'C':[],'G':[],'T':[]}
    for i in range(0,len(motifs[0])):
        curr_column = [motif[i] for motif in motifs]
        total = float(len(curr_column))
        for base in ['A','C','T','G']:
            the_matrix[base].append((curr_column.count(base) + 1) / total)

    return the_matrix

def most_common(lst):
    return max(set(lst), key=lst.count)

def find_consensus(motifs):
    consensus = []

    for i in range(0,len(motifs[0])):
        column = [motif[i] for motif in motifs]
        consensus.append(most_common_oneliner(column))

    return ''.join(consensus)

def score_motifs(motifs):
    consensus = find_consensus(motifs)
    score = 0
    for motif in motifs:
        score += HammingDistance.calc_dist(consensus,motif)

    return score

def greedy_motif_search(dna,k):
    best_motifs = []
    best_score = sys.maxint
    for seq in dna:
        best_motifs.append(seq[:k])

    first_seq = dna[0]
    rest_seq = dna[1:]


    for i in range(0,len(first_seq) - k + 1):
        kmer = first_seq[i:i+k]
        motifs = [kmer]
        for seq in rest_seq:
            profile_matrix = create_profile_matrix(motifs)
            motifs.append(find_most_probable_profile_kmer(seq,k,profile_matrix))

        curr_score = score_motifs(motifs)

        if curr_score < best_score:
            best_motifs = motifs
            best_score = curr_score

    return best_motifs

def get_rand_substring(string,k):
    try:
        index = random.choice(range(0,len(string) - k))
    except IndexError:
        raise Exception('Bad input: %s' % string)
    return string[index:index+k]

def randomized_motif_search(dna,k):
    import random
    random.seed()
    best_motifs = []
    best_score = sys.maxint
    for seq in dna:
        word = get_rand_substring(seq,k)
        best_motifs.append(word)

    while True:
        motifs = []
        the_matrix = create_profile_matrix(best_motifs)
        for seq in dna:
            kmer = find_most_probable_profile_kmer(seq,k,the_matrix)
            motifs.append(kmer)


        curr_score = score_motifs(motifs)
        if curr_score < score_motifs(best_motifs):
            best_motifs = motifs
            best_score = curr_score
        else:
            return (best_score,best_motifs)
#@timing
def gibbs_sampler(dna,k,n,start_set = None):
    best_motifs = []

    # Initialize with a given set
    if start_set:
        best_motifs = start_set

    # Initialize best motifs as random kmers
    else:
        for seq in dna:
            word = get_rand_substring(seq,k)
            best_motifs.append(word)

    # get score
    best_score = score_motifs(best_motifs)

    # Initialize copy
    motifs = [x for x in best_motifs]

    # Trial loop
    #pdb.set_trace()
    for i in range(0,n):

        # Pick a dna seq
        index = random.choice(range(0,len(dna)-1))

        # Remove from motifs at random index
        motifs.pop(index)

        # get profile matrix
        the_matrix = create_profile_matrix(motifs)

        # get random wieghted kmer
        new_kmer = find_most_probable_profile_kmer(dna[index],k,the_matrix)
        #new_kmer = get_weighted_random_profile_kmer(dna[index],k,the_matrix)
        # Insert into collection
        motifs.insert(index, new_kmer)

        curr_score = score_motifs(motifs)
        if curr_score < best_score:
            best_motifs = motifs
            best_score = curr_score

    return (best_score,best_motifs)



def main():
    x = ['CCCCGCACATCGGAAGCTCGCACGATTGCGAAAAGATGAGCCCCCTGAAGGTCAAAGTTATTTGAGTTCACCCCCCGATAGAAATGTCTTGAGTTTCTAATCCTTTGGCGCTAACCTTGTTATCCGGACGTTAGGATGATAAACTAACTATGGTTCGCTAACCCCCGCACATCGGAA',
'GCTCGCACGATTGCGAAAAGATGAGCCCTGTGATCTAGTCCCGCCTGAAGGTCAAAGTTATTTGAGTTCACCCCCCGATAGAAATGTCTTGAGTTTCTAATCCTTTGGCGCTAACCTTGTTATCCGGACGTTAGGATGATAAACTAACTATGGTTCGCTAACCCCCGCACATCGGAA',
'TTATCCTGGACACTAAACACGGGACCCAAAGGTCCCCACAGTTTTGACTGGACGAAGGGCAACCCCTGCATGGACTGCTCCCCAACTAAGCCTATAAATTGACTGGATAAGAGAGCGAGTCGGCACCCTGCATAATCGGCCTAATGTCGTGTAGTCCCGCTACGCCCCTTGTAATCC',
'AGCGTGTCTACTTGCGAATGATCTCCTAGAGACAACTTCCCCGCCAAGACCCGCTAGGCGCCAAACTCACCCTAACATCCGTTTGCCTAGTCCGTGATGCCTTTGAATGATGGTTAAAGAGCTGCTCGATTCAGAACTACCCTCTGTCCGAGAGTCCCGCAGTAGTTGATACACGGC',
'TAGCTAGGAACCACTAGTCCCGACCCCATTCTCAACGGTCTCGCTCAAGGGGGAGCTTCAACTAGTCTCCTGATAGACCATTTGCATATTTACAGGTCTTTGCGGCCGTAACCTATCGTCCGAATACGTCCTATACGCCGTCGTCAGACGAGTACTGATGTGACTGGGATAGCGACG',
'TTACTCTTTAGTAGGATGAACTTGGAGGAAGAACTAGGTAATGGCGCTTTCTATTGTCCGACAGTCCCGCTTCATTATTAGCAGCGGCCGTTGTATCGCCGACCGACGAACGGGTAGGGCAAGCCTCTGGGTAACGTTATCCGCTACCCTGGCGCCCTTACGAAGTCGTCGACCCAT',
'GGCTACAACTAGAGTATAAGAAGGTGGACGCCTGAGGTCGGCGTTCCTCTGAAGCTTGCTTGAGATTCATTTCGAACCTGTGTTAGATGGGTATCGTCACGTCCGATTATGGGATGGCGGTGTTTTTCTGGACAATATGTCATCACTAGTCCCGGGAGCTGATCTTCGCCATGATCA',
'CCATACGGGCGAAAAGCCGTTTGACACGGCTTGCTGTCGTTCTGCTGCGGCTAAGTAGGTTGCGTCCACTAGTCCGCAAAAAACTCGTGCAGTTGCGAGGGTAGTGGCATCGAAAAATGAGGCTCCCTGAGCACTATTTATATGATGTCTAACAGCGAGCTAGCCGGACGCTTCGGG',
'AGTTACTCTCGATCGGGTTTGCCAGTAATCGGTCAGGTTAGGCCCCTATCGGGGGCTATGGAGATCATCCAGGCATAGTAAACACGCTTGCCTGGCGGAACTATGCAGCAGCACACCTGTCCAGGTGTCCCGTCTGATCTTGCTGACTCATAAATATCTTTGCCGAGTCCCCTCCTT',
'CCGAAGAGACTGAGGCCAAAACGGGGCGGTGCTGTGATTCTTGTGATAGTGGAGATTCCGGTCCCCTGCCACTCGCACTACGGGCTTGGCGTGCCCAGGCCGGGTACGAATACCAAGGATCACCTATTGTCCACTGCCCCCGGAGAAAGGGCGGGGAAAAGGCAATGTCTGCCTAAA',
'GGTTAGCTCTCCTCCGATGACGCACGGCGCAGTAACGTATCGCCTGGGATATCCCCGGCTACGTGGTAGCATCCTCGCGGGGGGGAAGTGTTAGCTAGTCCCGCAATCAAGCCGGGCTACGTCTTACGCTGTAGCTTGATTTAGGCATGATCTGGCGAGACACCCGGTTCAAAGCGC',
'ATATTTAACACTCTGTGCATGGGCTTATACCCGTGTGCGGGGTTGGGCCGGATATTACCTTGTCAACTTTAACTATCCGGACGGTTCGAATTCCACTACTCACTCTGCACCTCGTATCGTGTTCACTGCTCGTAGGTACTTTACCACTCCTGGGGTTCATCCACTAGTCCCTAATGT',
'ACCGAAAATGATATCCCCAGACTCCGATTTGCCTCTGTGTACTAGCTACGCTGTCCATATGTCCCGCTCCATTCAGAAGGTTATCTCTTTCGAGCCCAGGAATCGTTTCCACCAGAGACCTCAAACCGTCCGCAGTAACTACGGCACTAATACATGGATTCAGCTGCACCTACTGTG',
'TTGTCCACTAGTGGGGACTGGGTGCGAGCGCAGTCCTAGAAAACGCGATTCGGGTCACTGAACCGCGAAGAGTGGGCACTACACACCAGTAAACCTTATTAGCGCGAGTATAACCCAACGCAATTATCCTCCATAGGTTGGATGCAGGGTGACCTACAATATAGTTTTCGCTAACTA',
'AAGGTTGTCCACTAAATCCGCGAATAGAATTTACCGATTTCCTAATCCCGAACATACCAACGGCTATCGGTGAATGGTATGATACGCCGGGGCGGGTCCTCCGGAGTTTCATTCATTTCCGCGTCCCATAATTAGCTGGCGGCCTAGAAGCTCAGTAACGCCAAAACTAATTATTTG',
'TTGTCGGAGCACATGACCCGTACCACAGGTGTGCAACACTGGACCAATCTAACGGGTCGTCGAGGACGTGTCCACTAGGAGCGGGGAACCATAACCTTGGCAAGCACTCATCTCTCCACTCGTGAGGCACCCCGGCTGCCCGCCTTGACGCAGCGGGGAGTGTTTAACTCCCGCGAT',
'ATGGTTTAATTGCCAGGTCTCTGCGGACTAGTCCCGTAGATCGTCTGTGACGCCAGGGGGCTCGAGTTCAACGCTAGAGCACGTCTACTACTCCTTCCAGTACATTCTACAGAACCCCATATCGTGCGTGTAAACCCACCCAAGAAATAAGTGGAATACAATAAGGGTTCTCTTAAA',
'GCTCCTGAGATGATGTTTATTCCGGGCGTTATAACAATGGTTACCGGAAGCATAGCTGCGCCGTGCGCGCAGTAACACTTATCACTCGCGGGGGCAACTACGTGTTAGTCAAGGCTTACATGGGTGGCGATCGGCATGTCGTACGTTTGTCTGATAGTCCCGTGGTGCAAGCTCTAG',
'ACTCATCATCAACAAAAGTTGCAGAAGAGGGCAAAACACCACTGAACCAGAGTTTAGATCGTGATGTCCACACCTCCCGCCTCGTCTCGGCGGTCGCCCAGCTGCCCCGGTTGCGCCGCTCAAGAACTCGTATAGGTCAGCATTATAGTCTTGGGTCTCTGGAGATTCGCGGGGTTG',
'GTGTTTAATGTTGACCGACGGAGCTAGCAGCGTCGTAGAAGGTAGCTGAAGTATAGTAACGAGGGCAATTACCCTTTTCGCGACGAATCTGAGCCCTGTCCACTAGTCGTCGGTCATACCAAGCGTGAGATCCCCTCTATCGCCCAGTACGATAGAAACGTCTGATATATTATTATC']
    best_score = sys.maxint
    best  = []
    for i in range(0,1000):
         temp = randomized_motif_search(x,15)
         #print temp
         if temp[0] < best_score:
             best = temp[1]
             best_score = temp[0]

    print best_score
    for i in best:
        print i


if __name__ == '__main__':
    #main()
    fin = []
    for x in range(3):
     #    z = ['CGCCCCTCTCGGGGGTGTTCAGTAACCGGCCA',
     # 'GGGCGAGGTATGTGTAAGTGCCAAGGTGCCAG',
     # 'TAGTACCGAGACCGAAAGAAGTATACAGGCGT',
     # 'TAGATCAAGTTTCAGGTGCACGTCGGTGAACC',
     # 'AATCCACCAGCTCCACGTGCAATGTTGGCCTA']

        z = ['TCACAAGAACACTATGGTGAGATTTCGCACGCTGTCCTTCTCGCCAGTTACCTTGGAGTCCAGATCTCCAAACTCCCCGCCCTAACGTCACTTACGATGCCATCGTCGAAACGTGTGGATCCCTTCTTAGGATAGTCCCTTGCGCAGTAGAGGCGGAACTCAGTCCTTGATGATGGGGTTCACACATGCGGGTTATATATTACGGCTGGGGTTTGTGTACCTCACTGTGACTTTTCAAAGGAAAGTAATGTACATTCAACTAACCATCCGCGGTGCCGGGTCCACGTCCTACTCGGCTTCCTCCACAATTTTGGATCACAAGAACACTAT',
'GGTGAGATTTCGCACGCTGTCCTGGCGTTGTTATGTGTTCTCGCCAGTTACCTTGGAGTCCAGATCTCCAAACTCCCCGCCCTAACGTCACTTACGATGCCATCGTCGAAACGTGTGGATCCCTTCTTAGGATAGTCCCTTGCGCAGTAGAGGCGGAACTCAGTCCTTGATGATGGGGTTCACACATGCGGGTTATATATTACGGCTGGGGTTTGTGTACCTCACTGTGACTTTTCAAAGGAAAGTAATGTACATTCAACTAACCATCCGCGGTGCCGGGTCCACGTCCTACTCGGCTTCCTCCACAATTTTGGATCACAAGAACACTAT',
'GAGGATCAATTAAGATCTCTCCCGTCTATCGGTATGTCTTGGGTCACCTTGTTCAGCTTCCAGATATGCAATTTTTGCTTTCGAAACAAAGGTAGAACATCCGGCAGCAGGTTGGGGACGCGATGTGCCGGACGCGTAACCTTATCCCGTAGGGAGATACTCTAGGTCCCAGTACGGATGCAAGGTGAATGCACGGGGCGGCCGGACCTCAACGTCCCAGGCGAGCTAATGCAGTTCGTTGCTACCAGCTGCGACTGTTATGTGTTTTGCTCCGACTAGGGAGGAAAGTTAACTTAGACCAACTTCGTGTCCGTTGGACTTCCAACTCCC',
'CGCGTGCGGTAACTCAACCGTCGCAGGTAGAGTGGTGGATCTGTTCGCTGTACCATTAACTATTCAGTTGAATCGTACTTCCTCATCTCCGACTGAGAGTGGTCGATGACAAAAGAAGAGTTAAATATTGCCCATTGGCAAATAGGCCTAAATAACTGTCAGGGCAGGTGTTTCCCCACCCTTTATGCCCCGATTTAGTGTGCGGTCTGAAAGTACTCCCCTCTAGGACTCATCTGTCCACTCTGTGTCCAGGCATCATCTGAGACCCCGTTGTTGCTGGAGCATTGCAGTGTCACCAATTGGCGCGATCTAGCTATTTTGTCAGAGAAC',
'TCTCGTGAATGTTGCTTGTCACGGTGAAAGGGGGTGCTCGTATGATGACTCCATACCAGAACGAGGCCATCTGTTATGTGCCATCGTGGCTTGAGGTGTAAGTATACTGCCCCTACCCAGCCTTCCCGACTTATAACTAGCCAAGCTGCCACGCTATGCTTAGTTTCTAGCTCTGCCCGTGGGTTATTAGCTTACCGAAAGAGCGCACGTTACAGAGATTTCTCGTAACAACGTCGCAGAAGCATCAGTCGGCAGAGCAGTCTAGAAGACCGTCACTAGGATGGCCAAACGTCTTTTGTGAATGTATATGACCCATGTACGTATATTGCC',
'CCTGGATCGAATATGTGAACTAACGAGAGACGACATATGCCAAACGGGGAAACTAGCGAAACAGTTCGAACTAGATGGGCACTACGCTGGAGTCAACCGCTGGTTACATCAGATTGAAACAGCACCTCCTTGGCAACTCAGACGATTTATACTCGAATCTATCATGGGTTAAGTGGCTTCCTGCATTAACACACTTCGCCCCTACGTGTGCTGCGACGACTCCCCGATTACAGCGGGCACTGCCGACTGCGGCCACGAGTTGCGAAGGACGCGCACCAAGCTTCACCCCTAAATAAAACCTCTATAACCGCCCCGCGCTGGGCCCAGGAG',
'TGACCCTCGAGTGTAGTATCGTGCACATATCGCTAAAGTCAGGTCTCCCAGCTCGTTTGGGTTACTAGCCGATCTATCCGAGCCAAAGGTGATGACGCCAAACACCTGTCTTACACGAAAGATCTGTTATGTTCAACATGTGGGCGTTCGGGGAGCTGCTAATTTGCCATTGCTAAGAGTGCAGTCTGGAGAACCACTACTTGAGCGTAGGAGATTCTACCATCAAGTAAACCAGCGGGATAAAGTATCGTGATGTTCAAAGGCCAACATTGCCAAGCAAGACGTAACTCACATTTGCTCTTGTCCTTGGTCACGGCTAGACCTCCGCTA',
'CAGACACTTCCTACTGCCTTATGTCCATTGTTGTGAACGTCTCTTGCTATGAGCATCTCGGTGAGTTTGTCACGTGTATATCAAGCTTGTAGACTAGGCCCCGTCGCTGGGAGTGCTCTTACGACAACAGACAAACGTGGATCGAGTATGTGGTCATCCAGCAGCCCATCTGCCGAAGCATACATGCTCCTGAAGCCACGGTCCGAACCTACTAATACAGATTGCCCGCGGCCCCCGGCTCCGTCTCGTCCAGTATCAGTTAGGGGGACGCGCAGCATCGACCCAAGGCAGAAAAGAATCGTACCGTAAGCCTTGTGCATATCTCGGGAT',
'CGCATGGAGAGCCCTGGTGAGAAGACGGGGCTTTAATTAGGCGTTGCAAACCGTATAGCGACGTGTAGGGCAGCTTGCTTAGCGCATCCCGCTGTCCAGGGGAATCTCTTGAGATATAGCCTAAGGCGAGATCTAAACCAAAAGAGTCTAGGGCGCAAGGGACTGGAGTCCCGCTAAAAATGGACTTGAATGCGAAGGATCTGTTATGGATCGGCGACGCGCCGAGCGAACGGTATCGGACCAGACTATATTAATTCCAAGTATCGAATCCTATCGTAAGGGGGTGATAATTTTCCGTGTGAAAAAGGCTTTAATCCTTGAATACGGAGC',
'GGGCACTGAAGTTCCAGATAACACCTGGATGGTTTATGTGTGCAGAAAATTCTGCAATTATTTTTGCTGACGCATCCTGCTACGTAGTATCTCCTTTGGTGACCTCATAGTCCACCCCCTCCGGAGGGCCTAGTAAAAAGGTTGACATTGCTCGTCAGTGAAGGGTTAATCTCGCAATCGTTATCTAGTTACAAAGTTGCCGTCAGTTCATTCTAGCCTAACTTCGATGTTCGAAGCGGCGGCCTATTCGACCATCATGTCTTGAGGTCTAAACACCTTTGTGCTGCCTCTGGTATATTGCAGGCTAACGACTAACTTTGGATACCAAAC',
'TTAAACTAGACGAGATAATTAAGAAAGCATTTTTTGGGTTAGATCTACTCTGCGGTTATACCCGTACTACTGATTGACGACCCTGCTAGCGTCCCGCCCTTAAACGTCCGAAGCGAAGGGAGGACGTGGTCGATCAATATCCGAATACGCTATTTTCAGCTTCCGGTGTCAAGTGTATGACCCACTACCGCAATTAAAACTACGCTATTCATTTCTTCACACGCGTTGGATCTGTTATAGAACAATTCCTACTGGCGGCCGAAACACAGGTAATACGATACGCGTTACACCTATACAGTTTAATACTCGACAAGGATGATTGAGGAAGTT',
'TCGAAGTCTCCAGCAGCTAATTGCTAGTAGCAGGATTGGCAGCTGATCTTGTGAGGTGCGTGTGGCCAATGTGGAAGCTCATACTGTGTCACAATCGTAGGAAAAACTCATTTTCTGGACCCGTTAGTTGGATTCATTATGTGTGTACAGTGGATGCTCGACACGTCTGAGGCTAATGCTGATATCTAGCTACGCGACATACAGCACCTGGGTAAGCTTACCTCGGGGATTCTTGTGGGGAGTACAGCGCTCATACAGACTCAGACCTGCTCAGATCGCTGAAATTAATTCCTCGCCTGCAGGGCCGAAGGCCCATGCCCGGTGCGCGGC',
'GCTTGACTCGTGCCGCGGGATCTGACATTCCAGAGATTCCTATGCCCTACGATTTGGTATTGTTATGTGTGCTTGACAGTCCTTGTAGGCATAGCAGGCAGTAATATATACTATGTGTACCAATCACGCAACCTCCGGGTTCACTGGTGTAATGGCTACAGACCACAATGTTTAGCTCATCAATAGACCCGAAATTTTGTGGCGGCGACTCGAGCGCTCCGGTGTGCATCGTCTATCCTGGTACTCTCTAATAGGGCTAAACGGGTCCGCTAGCACGCATCAATCGGGGAGCACGACTACAACGTCACGAGGGGACTTACCAAGGTACGT',
'CGATAGGTTTAACAGGAACTGTTATTTCGGTAAGGCGGACAGGCTGGCTTATAGCATACGGAAGCCGGTAATACAGAAGACAAATTGCAATATGGGTGGTAAGGAGCACACCCGGATTGGTTGGCCTAGACAAAAGATCGGCTTGCGCCTTTTCACAGGCCTTACCTTCCCGTGGATCTGTAGGGTGGTGGTCTTTTTGCTGGTCGGAGGGACTAACGATCTCTAGAAGCCATATCGCAGAGGAGCAGCCGGCCCTCCTCAAGAACGGGACACATCAAAGGTGATGTAACGACTCTACGTTAGGGGAGAGCGCAGGTACTCGAATTGCAT',
'CACCGCAAGGATGAACTTTTCGAGTTCGTCGAAGCTCAGGGCCATTCGTGAATAGAGTACCCGTATCACTCTTCTTATGGTACCGTGGTCAATACCAATTTGACTAGTTCGCTCGCCCCTGTTACGCCCGGGAGTAATTCCCCCTATACGGTAGCTTAGGCCAGATATGCAATGAATCGTGGGCGTGGTGCGTGAGCATGCGTTTCAGTGGATCTGAATTGTGTTAGCTTGACACAATCTTAGGTGTTCGACTCGTTGATACAGGACGATGAAGGCATCTCTAACTCAAAGTTTTTTTACTACTTGGCCTAGGCTTGCTTGGAGGGCGGA',
'AAAGGTGGGCGGAGGGTGTGCACAGTTATATTATAGACCGAGCAGACACTGATCAATTCCATGCAGAAAATAACTATTATTCGTTGATTATTTCACTGGATTCATAAGCAGCTGCCTCCGTGTAAAGGAGCACATTGTGATTGGTAGGTCTCGAGCAGCGGAGCTCTTTTTCACACCTCAGGGTGCAATATATCTTTATGGATCTGTTAATGGACTAACCCTGTCCGCGATTAGGCACAGTAAAAGACTTAATCGAACCTGTTTGAAAATGCGACTGGCCAGGATACGTAACCATTTATTTAGAGATACCAATCGGGCAGACTTCCCCCT',
'CTTATTTGCCCCACCGTTAATGGATGCTGGCCAGTTCGCTAGTTGGCGGTCCGTGTGACGGATATGTCTGTTATGTGGTGTTGAACGGCCGGCCAGTTACCGTTGGCTGCCGTATAGAAGCCGTTTATATCGACTACCGGGCGGGAATACCACTACGGAGGCTGTGCGGGAGCTTGACCTCGATCAAGCTTTCGACATGTCACCTTCACGCAGGGCCAGGGCTGGTGCCGGGACGTGTAAAGGAGAGTAAGTCAGGAAAATCCTTACGGTTCCTCGGGCTACTTGGTTGATACGGGTTCGGGGGTCCTATATCTTTTTTGCCCACGGATG',
'GACATCGTCTTGGGGACCGTATTTAAACTATCATCGATGGAGTATCATGCAAGACTCTAGGCACGGTGCAAGCCTGAGCCGAACTGACCCAAAGTATTAAGCCTCGCGGCTTCCGAACGGTGGGCGGATGTACTCTTTGGATCTTGGATGTGTAGAAGTCCGAACTCTCGAAACTTAGACACCGCGCCTGGATTCCTATTTCCGTCACTCATCGTGAACTTCATTAGAGCTAAGAGGCTCAACCTCTGAGTGGGCGACGGTATGTCTCAAGAATGGTCAGGAACGCGTTACATCCGATATCAACGTATTGTCGCACTGCACCCGCAAAGT',
'GCCCCTAGTATCCCCTTCACAATCATGGCCGTGCACGGACGGATGGAAACGTTATGTGCGTGTGGCCGGGTTCTGGGCATTTGAACCCACGCTGATATCGCTGATTGCGTACGTTCGGGCGCAGAATGTACACTTCCGTTCAACGCCTCATGCCGGGCGGCGAGCGGACATCTACTATTGTGCTACAAGGCGTTTGCTTTCCTATTGCTCGTCGCGTAGAGATGGGGTGGATCTTATGAGCTCCGCGACACTTTAAATTGAGCCAGGGGGTGTCGATCAAATTACAGCATTCTTGAACCGCCACCCCGGTGGCCCTCAGGAATCCCGCCT',
'TCTTGAACTGATCCTGGTACGTAAGTGAAGCCACGCGAAAGTGTAGGTTGGCAGCACTATAATTGGAATCGTTATGTGATCGGGTGCGAAGTGAGTACGGTATAGGGCCCCATGTGAACGAGTACTCTGGGGCACGCAGAAGAAGTCCGAAATCCATGATACTTGTCGCTGCGGGGAGAGTAGATAGCTCTAAAAACTCGTGACGCCCGAGTGACAGAACGCCCAGCCCTAAAGGCAGCCTGTCCGCCTTTAAAACGATATTTACTAGCGCTTACGAGAGCTTAAGTTGGCCTCTGGAACGGTGCACGAGGAATACCCCGCGACTCACAC']

        max_score = sys.maxint
        for i in range(0,90):
            temp = gibbs_sampler(z,15,100)
            if temp[0] < max_score:
                best = temp[1]
                max_score = temp[0]
            # if temp[0] <= 9:
            #     best_1.append(temp[1])

        fin.append(gibbs_sampler(z,15,1000,best)[1])

    for x in fin:
        print 'NEW:'
        for i in x:
            print i

    # actual = []
    # for i in range(0,len(fin[0])):
    #     column = [x[i] for x in fin]
    #     actual.append(most_common_oneliner(column))
    #
    # print actual

    #print max_score

    #for i in best:
    #    print ir