algorithmgenomics

Naive algorithm with character comparison and aligments count


i was asked to code a modified function of naive excat matching that also counts the number of character comparisons and the number of alignments made. The original code was the following:

def naive(p, t):
    occurrences = []
    for i in range(len(t) - len(p) + 1):  # loop over alignments
        match = True
        for j in range(len(p)):  # loop over characters
            if t[i+j] != p[j]:  # compare characters
                match = False
                break
        if match:
            occurrences.append(i)  # all chars matched; record
    return occurrences

When I test my code, it gives back this error:
ValueError: not enough values to unpack (expected 3, got 1)
I know that is because some of the variables weren't correctly defined, but i got stuck and don't know how to fix it

def naive_with_counts(p, t):
    occurrences = []
    num_character_comparisons = 0
    num_alignments = 0
    for i in range(len(t) - len(p) + 1):# loop over alignments       
        num_alignments +=1
        match = True
        
        for j in range(len(p)):  # loop over characters
            if t[i+j] != p[j]:  # compare characters
                num_character_comparisons+=1
                match = False
                break
        if match:
            occurrences.append(i)  # all chars matched; record
    return occurrences
    return num_character_comparisons
    return num_alignments
p = 'word'
t = 'there would have been a time for such a word'
occurrences,num_character_comparisons, num_alignments = naive_with_counts(p, t)
print(occurrences,num_character_comparisons, num_alignments)

Solution

  • The problem is in your code not in the algorithm. You're trying to return multiple values from the function which is not the proper syntax. You're can return those values as a tuple or a dictionary.

    def naive_with_counts(p, t):
        occurrences = []
        num_character_comparisons = 0
        num_alignments = 0
        for i in range(len(t) - len(p) + 1):  # loop over alignments
            num_alignments += 1
            match = True
            for j in range(len(p)):  # loop over characters
                num_character_comparisons += 1
                if t[i+j] != p[j]:  # compare characters
                    match = False
                    break
            if match:
                occurrences.append(i)  # all chars matched; record
        return occurrences, num_character_comparisons, num_alignments # <-----Here
    
    # Test the function
    p = 'word'
    t = 'there would have been a time for such a word'
    occurrences, num_character_comparisons, num_alignments = naive_with_counts(p, t)
    print(occurrences, num_character_comparisons, num_alignments)
    

    CODE DEMO