<jupyter_start><jupyter_text>**Chapter 2** **Task1:**http://rosalind.info/problems/ba2a/Implement MotifEnumeration<jupyter_code>def neighbour(pattern, mismatch, words):
    if mismatch == 0:
        words.add(pattern)
    else:
        bases = ['A', 'T', 'C', 'G']
        for i in range(len(pattern)):
            for j in range(len(bases)):
                new_pattern = pattern[:i] + bases[j] + pattern[i+1:]
                if mismatch <= 1:
                    words.add(new_pattern)
                else:
                    neighbour(new_pattern, mismatch-1, words)

def MotifEnumeration(dna, k, d):
    patterns = []
    for n in range(len(dna)):
        pattern = set()
        for i in range(len(dna[n]) - k + 1):
            kmerspattern = set()
            neighbour(dna[n][i:i + k], d, kmerspattern)
            for words in kmerspattern:
                pattern.add(words)
        for j in pattern:
            patterns.append(j)
    motifpattern = []
    for element in patterns:
        if patterns.count(element) == len(dna):
            motifpattern.append(element)
    motifpattern = list(set(motifpattern))
    return motifpattern

if __name__ == "__main__":
    k, d = 3, 1
    dna = ['ATTTGGC',
           'TGCCTTA',
           'CGGTATC',
           'GAAAATT']
    # with open("rosalind_ba2a.txt", "r") as f:
    #     k, d = map(int, f.readline().strip().split())
    #     dna = [line.strip() for line in f]
    result = MotifEnumeration(dna, k, d)
    for i in result:
        print(i)<jupyter_output>TTT
GTT
ATA
ATT<jupyter_text>**Task2:**http://rosalind.info/problems/ba2b/Find a Median String<jupyter_code>from itertools import product

def pattern_generate(k):
  bases = ['A', 'C', 'G', 'T']
  results = []
  for c in product(bases, repeat=k):
    word = ''.join(c)
    results.append(word)
  return results
    
def min_hamming_distance(pattern, string):
    min_distance = len(pattern)
    for i in range(len(string) - len(pattern) + 1):
        distance = sum([1 for j in range(len(pattern)) if pattern[j] != string[i:i+len(pattern)][j]])
        if distance < min_distance:
            min_distance = distance
    return min_distance


def find_median_string(k, dna):
    pattern = pattern_generate(k)
    distance_from_pattern = {}
    min_dist = len(dna) * len(pattern)
    for i in pattern:
        sum_dist = 0
        for j in range(len(dna)):
            sum_dist += min_hamming_distance(i, dna[j])
        distance_from_pattern[i] = sum_dist
        min_dist = min(sum_dist, min_dist)
    for i in distance_from_pattern.keys():
        if distance_from_pattern[i] == min_dist:
            print(i)
            break

if __name__ == "__main__":
    k = 3
    dna=['AAATTGACGCAT',
        'GACGACCACGTT',
        'CGTCAGCGCCTG',
        'GCTGAGCACCGG',
        'AGTACGGGACAG']
    # with open("rosalind_ba2b.txt", "r") as f:
    #     k = int(f.readline().strip())
    #     dna = [line.strip() for line in f]
    find_median_string(k, dna)<jupyter_output>ACG<jupyter_text>**Task3:**http://rosalind.info/problems/ba2c/Find a Profile-most Probable k-mer in a String<jupyter_code>def probability_of_kmer(string, matrix):
    probability = 1.0
    for i in range(len(string)):
        if string[i] == 'A':
            probability *= matrix[0][i]
        elif string[i] == 'C':
            probability *= matrix[1][i]
        elif string[i] == 'G':
            probability *= matrix[2][i]
        elif string[i] == 'T':
            probability *= matrix[3][i]
    return probability

def profile_most_probable_kmer(string, k, matrix):
    kmer_probability = {}
    for i in range(len(string)-k+1):
        kmer_probability[string[i:i+k]] = probability_of_kmer(string[i:i+k], matrix)
    max_key = max(kmer_probability, key=kmer_probability.get)
    return max_key

if __name__ == "__main__":
    string = 'ACCTGTTTATTGCCTAAGTTCCGAACAAACCCAATATAGCCCGAGGGCCT'
    k = 5
    matrix = [[0.2, 0.2, 0.3, 0.2, 0.3], [0.4, 0.3, 0.1, 0.5, 0.1], [0.3, 0.3, 0.5, 0.2, 0.4], [0.1, 0.2, 0.1, 0.1, 0.2]]
    # with open("rosalind_ba2c.txt", "r") as f:
    #     string = f.readline().strip()
    #     k = int(f.readline().strip())
    #     matrix =[[float(l) for l in line.strip().split()] for line in f]
    print(profile_most_probable_kmer(string, k, matrix))<jupyter_output>CCGAG<jupyter_text>**Task4:**http://rosalind.info/problems/ba2d/Implement GreedyMotifSearch<jupyter_code>def probability_of_kmer(string, matrix):
    probability = 1.0
    for i in range(len(string)):
        if string[i] == 'A':
            probability *= matrix[0][i]
        elif string[i] == 'C':
            probability *= matrix[1][i]
        elif string[i] == 'G':
            probability *= matrix[2][i]
        elif string[i] == 'T':
            probability *= matrix[3][i]
    return probability

def profile_most_probable_kmer(string, k, matrix):
    kmer_probability = {}
    for i in range(len(string)-k+1):
        kmer_probability[string[i:i+k]] = probability_of_kmer(string[i:i+k], matrix)
    max_key = max(kmer_probability, key=kmer_probability.get)
    return max_key

def score(Motifs):
    count_score = 0
    for i in range(len(Motifs[0])):
        j = [motif[i] for motif in Motifs]
        count_score += (len(j) - max(j.count("A"), j.count("C"), j.count("T"), j.count("G")))
    return count_score

def greedy_motif_search(Dna, k, t):
    BestMotifs = [dna[:k] for dna in Dna]
    for k_mer in [Dna[0][i:i+k] for i in range(len(Dna[0])-k+1)]:
        Motifs = [k_mer]
        for i in range(1, t):
            motifs = Motifs[:i]
            matrix = []
            for base in ["A", "C", "G", "T"]:
                row = []
                for j in range(k):
                    col = [x[j] for x in motifs]
                    #print(col)
                    row.append(col.count(base)/len(motifs))
                matrix.append(row) 
            Motifs.append(profile_most_probable_kmer(Dna[i], k, matrix))
        if score(Motifs) < score(BestMotifs):
            BestMotifs = Motifs
    return BestMotifs

if __name__ == "__main__":
    k, t = 3, 5
    Dna = ['GGCGTTCAGGCA',
            'AAGAATCAGTCA',
            'CAAGGAGTTCGC',
            'CACGTCAATCAC',
            'CAATAATATTCG']
    # with open("rosalind_ba2d.txt", "r") as f:
    #     k, t = map(int, f.readline().strip().split())
    #     Dna = [line.strip() for line in f]
    BestMotifs = greedy_motif_search(Dna, k ,t)
    print("\n".join(BestMotifs))<jupyter_output>CAG
CAG
CAA
CAA
CAA<jupyter_text>**Task5:**http://rosalind.info/problems/ba2e/Implement GreedyMotifSearch with Pseudocounts<jupyter_code>def probability_of_kmer(string, matrix):
    probability = 1.0
    for i in range(len(string)):
        if string[i] == 'A':
            probability *= matrix[0][i]
        elif string[i] == 'C':
            probability *= matrix[1][i]
        elif string[i] == 'G':
            probability *= matrix[2][i]
        elif string[i] == 'T':
            probability *= matrix[3][i]
    return probability

def profile_most_probable_kmer(string, k, matrix):
    kmer_probability = {}
    for i in range(len(string)-k+1):
        kmer_probability[string[i:i+k]] = probability_of_kmer(string[i:i+k], matrix)
    max_key = max(kmer_probability, key=kmer_probability.get)
    return max_key

def score(Motifs):
    count_score = 0
    for i in range(len(Motifs[0])):
        j = [motif[i] for motif in Motifs]
        count_score += (len(j) - max(j.count("A"), j.count("C"), j.count("T"), j.count("G")))
    return count_score

def greedy_motif_search(Dna, k, t):
    BestMotifs = [dna[:k] for dna in Dna]
    for k_mer in [Dna[0][i:i+k] for i in range(len(Dna[0])-k+1)]:
        Motifs = [k_mer]
        for i in range(1, t):
            motifs = Motifs[:i]
            matrix = []
            for base in ["A", "C", "G", "T"]:
                row = []
                for j in range(k):
                    col = [x[j] for x in motifs]
                    #print(col)
                    row.append(col.count(base)+1/len(motifs)+4)
                matrix.append(row) 
            Motifs.append(profile_most_probable_kmer(Dna[i], k, matrix))
        if score(Motifs) < score(BestMotifs):
            BestMotifs = Motifs
    return BestMotifs

if __name__ == "__main__":
    k, t = 3, 5
    Dna = ['GGCGTTCAGGCA',
            'AAGAATCAGTCA',
            'CAAGGAGTTCGC',
            'CACGTCAATCAC',
            'CAATAATATTCG']
    # with open("rosalind_ba2e.txt", "r") as f:
    #     k, t = map(int, f.readline().strip().split())
    #     Dna = [line.strip() for line in f]
    BestMotifs = greedy_motif_search(Dna, k ,t)
    print("\n".join(BestMotifs))<jupyter_output>TTC
ATC
TTC
ATC
TTC<jupyter_text>**Task 6**http://rosalind.info/problems/ba2f/Implement RandomizedMotifSearch<jupyter_code>import random 

def probability_of_kmer(string, matrix):
    probability = 1.0
    for i in range(len(string)):
        if string[i] == 'A':
            probability *= matrix[0][i]
        elif string[i] == 'C':
            probability *= matrix[1][i]
        elif string[i] == 'G':
            probability *= matrix[2][i]
        elif string[i] == 'T':
            probability *= matrix[3][i]
    return probability

def profile_most_probable_kmer(string, k, matrix):
    kmer_probability = {}
    for i in range(len(string)-k+1):
        kmer_probability[string[i:i+k]] = probability_of_kmer(string[i:i+k], matrix)
    max_key = max(kmer_probability, key=kmer_probability.get)
    return max_key

def get_score(Motifs):
    count_score = 0
    for i in range(len(Motifs[0])):
        j = [motif[i] for motif in Motifs]
        count_score += (len(j) - max(j.count("A"), j.count("C"), j.count("T"), j.count("G")))
    return count_score

def get_random_motifs(Dna, k, t):
    motifs = []
    kmer_index = [random.randint(0, len(Dna[0]) - k) for i in range(len(Dna))]
    motifs = [Dna[i][j:j+k] for i, j in enumerate(kmer_index)]
    return motifs

def create_profile_with_pseudocounts(motifs):
    matrix = []
    for base in ["A", "C", "G", "T"]:
        row = []
        for j in range(len(motifs[0])):
            col = [x[j] for x in motifs]
            #print(col)
            row.append(float(col.count(base) + 1) / float(len(motifs) + 4))
        matrix.append(row) 
    #print(matrix)
    return matrix
        
def randomized_motif_search(Dna, k, t):
    Motifs = get_random_motifs(Dna, k, t)
    BestMotifs = Motifs
    BestScore = get_score(BestMotifs)
    while True:
        Profile = create_profile_with_pseudocounts(Motifs)
        #print(Profile)
        Motifs = [profile_most_probable_kmer(Dna[i], k, Profile) for i in range(len(Dna))]
        current_score = get_score(Motifs)
        if current_score < BestScore:
            BestMotifs = Motifs
            BestScore = current_score
        else:
            return BestMotifs, BestScore

if __name__ == "__main__":
    # with open("rosalind_ba2f.txt", "r") as f:
    #     k, t = map(int, f.readline().strip().split())
    #     Dna = [line.strip() for line in f]
    k, t = 8, 5
    Dna = ['CGCCCCTCTCGGGGGTGTTCAGTAAACGGCCA',
    'GGGCGAGGTATGTGTAAGTGCCAAGGTGCCAG',
    'TAGTACCGAGACCGAAAGAAGTATACAGGCGT',
    'TAGATCAAGTTTCAGGTGCACGTCGGTGAACC',
    'AATCCACCAGCTCCACGTGCAATGTTGGCCTA']
    allScores = []
    allMotifs = []
    for i in range(1000):
        motifs, scores = randomized_motif_search(Dna, k, t)
        allScores.append(scores)
        allMotifs.append(motifs)
    BestMotifs = allMotifs[allScores.index(min(allScores))]
    print("\n".join(BestMotifs))<jupyter_output>TCTCGGGG
CCAAGGTG
TACAGGCG
TTCAGGTG
TCCACGTG<jupyter_text>**Task 7**http://rosalind.info/problems/ba2g/Implement GibbsSampler<jupyter_code>import random
from random import randint

def probability_of_kmer(string, matrix):
    probability = 1.0
    for i in range(len(string)):
        if string[i] == 'A':
            probability *= matrix[0][i]
        elif string[i] == 'C':
            probability *= matrix[1][i]
        elif string[i] == 'G':
            probability *= matrix[2][i]
        elif string[i] == 'T':
            probability *= matrix[3][i]
    return probability

def profile_most_probable_kmer(string, k, matrix):
    kmer_probability = {}
    for i in range(len(string)-k+1):
        kmer_probability[string[i:i+k]] = probability_of_kmer(string[i:i+k], matrix)
    max_key = max(kmer_probability, key=kmer_probability.get)
    return max_key

def get_score(Motifs):
    count_score = 0
    for i in range(len(Motifs[0])):
        j = [motif[i] for motif in Motifs]
        count_score += (len(j) - max(j.count("A"), j.count("C"), j.count("G"), j.count("T")))
    return count_score

def get_random_motifs(Dna, k, t):
    motifs = []
    kmer_index = [random.randint(0, len(Dna[0]) - k) for i in range(len(Dna))]
    motifs = [Dna[i][j:j+k] for i, j in enumerate(kmer_index)]
    return motifs

def create_profile_with_pseudocounts(motifs):
    matrix = []
    for base in ["A", "C", "G", "T"]:
        row = []
        for j in range(len(motifs[0])):
            col = [x[j] for x in motifs]
            #print(col)
            row.append(float(col.count(base) + 1) / float(t + 4))
        matrix.append(row) 
    #print(matrix)
    return matrix
        
def GibbsSampler(Dna, k, t, N):
    Motifs = get_random_motifs(Dna, k, t)
    BestMotifs = Motifs
    BestScore = get_score(BestMotifs)
    for j in range(N):
        i = random.randint(0, t-1)
        Motifs.pop(i)
        Profile = create_profile_with_pseudocounts(Motifs)
        #print(Profile)
        motif = profile_most_probable_kmer(Dna[i], k, Profile)
        #print(motif)
        Motifs.insert(i, motif)
        current_score = get_score(Motifs)
        if current_score < BestScore:
            BestMotifs = Motifs
            BestScore = current_score
    return BestMotifs, BestScore

if __name__ == "__main__":
    k, t, N = 8, 5, 100
    Dna = ['CGCCCCTCTCGGGGGTGTTCAGTAAACGGCCA',
           'GGGCGAGGTATGTGTAAGTGCCAAGGTGCCAG',
           'TAGTACCGAGACCGAAAGAAGTATACAGGCGT',
           'TAGATCAAGTTTCAGGTGCACGTCGGTGAACC',
           'AATCCACCAGCTCCACGTGCAATGTTGGCCTA']
    # with open("rosalind_ba2g.txt", "r") as f:
    #     k, t, N = map(int, f.readline().strip().split())
    #     Dna = [f.readline().strip() for _ in range(t)]
    allScores = []
    allMotifs = []
    min_score = 9999999999999999
    best_motifs = None
    for i in range(20):
        motifs, scores = GibbsSampler(Dna, k, t, N)
        if scores < min_score:
            min_score = scores
            best_motifs = motifs
    print(*best_motifs, sep='\n')<jupyter_output>AACGGCCA
AAGGTGCC
AAGAAGTA
CAGGTGCA
CACGTGCA<jupyter_text>**Task 8**http://rosalind.info/problems/ba2h/Implement DistanceBetweenPatternAndStrings<jupyter_code>def hammingDist(genome, kmer):
    dist = []
    for i in range(len(genome) - len(kmer) + 1):
        word = genome[i:i+len(kmer)]
        dist.append(sum(x != y for x, y in zip(word, kmer)))
    return(min(dist))

def DistanceBetweenPatternAndStrings(pattern, dna):
    distance = 0
    for seq in dna:
        tempDist = [hammingDist(pattern, seq[i : i + len(pattern)]) for i in range(len(seq) - len(pattern) + 1)]
        minTempDist = min(tempDist)
        distance += minTempDist
    return(distance)

if __name__ == "__main__":
    pattern = 'AAA'
    dna = ['TTACCTTAAC', 'GATATCTGTC', 'ACGGCGTTCG', 'CCCTAAAGAG', 'CGTCAGAGGT']
    # with open(filename, 'r') as f:
    #     pattern = f.readline().rstrip()
    #     dna = f.readline().rstrip().split()
    print(DistanceBetweenPatternAndStrings(pattern, dna))<jupyter_output>5
{'fraction_non_alphanumeric': 0.14386595621750017, 'fraction_numerical': 0.011427104063683637, 'mean_word_length': 2.6118710874101554, 'pattern_counts': {'":': 8, '<': 32, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '514327', 'license': 'MIT', 'n_tokens_mistral': 5905, 'n_tokens_neox': 5683, 'n_words': 1183, 'path': 'Chapter_2.ipynb', 'repo_name': 'sharmin6630/Bioinformatics-Rosalind-Textbook-Track', 'size': '15577'}