Greedy Sequence Search Algorithms in Python

1. Finding the Longest Consecutive Nucleotide Sequence in DNA

In this example, we'll implement a greedy sequence search algorithm to find the longest consecutive sequence of a given nucleotide within a DNA sequence. Let's say we want to find the longest consecutive sequence of 'A' in a DNA sequence.

    
    def greedy_dna_sequence_search(dna_sequence, target_nucleotide):
        if not dna_sequence:
            return ""
    
        # Initialize variables to store the current sequence and the longest sequence found so far.
        current_sequence = ""
        longest_sequence = ""
    
        for nucleotide in dna_sequence:
            if nucleotide == target_nucleotide:
                # If the current nucleotide matches the target nucleotide, add it to the current sequence.
                current_sequence += nucleotide
            else:
                # If it doesn't match, start a new sequence.
                current_sequence = ""
    
            # Update the longest sequence if the current sequence is longer.
            if len(current_sequence) > len(longest_sequence):
                longest_sequence = current_sequence
    
        return longest_sequence
    
    

How the Algorithm Works:

The algorithm iterates through the DNA sequence, checking each nucleotide.
If the current nucleotide matches the target nucleotide ('A' in this case), it extends the current consecutive sequence.
If a mismatch is encountered, a new sequence is started.
The algorithm keeps track of the longest consecutive sequence found.

Let's test the algorithm with an example:

    
        dna_sequence = "AAATGCTTTCGGGAAA"
        target_nucleotide = "A"
        result = greedy_dna_sequence_search(dna_sequence, target_nucleotide)
        print(result)  # Output: "AAA"
    
    

2. Finding the Most Frequent k-mer in DNA

In this example, we will implement a greedy sequence search algorithm to find the most frequent k-mer (substring of length k) within a DNA sequence. We will search for the most frequent 2-mer (di-nucleotide) in the DNA sequence.

    
def greedy_dna_2mer_search(dna_sequence, k=2):
    if not dna_sequence or k <= 0:
        return ""

    # Initialize a dictionary to store the frequency of k-mers.
    kmer_count = {}

    for i in range(len(dna_sequence) - k + 1):
        kmer = dna_sequence[i:i + k]
        if kmer in kmer_count:
            kmer_count[kmer] += 1
        else:
            kmer_count[kmer] = 1

    # Find the most frequent k-mer.
    most_frequent_kmer = max(kmer_count, key=kmer_count.get)

    return most_frequent_kmer

    
    

How the Algorithm Works:

The algorithm iterates through the DNA sequence, extracting k-mers (2-mers in this case) in each iteration.
It maintains a dictionary to count the frequencies of each k-mer.
After processing the entire sequence, it finds the most frequent k-mer.

Let's test the algorithm with an example:

    
        dna_sequence = "ACGTACGTACGTATCGATCGT"
        result = greedy_dna_2mer_search(dna_sequence, k=2)
        print(result)  # Output: "CG"
            
    

Conclusion

In this blog post, we've explored two different examples of greedy sequence search algorithms in Python. The first example finds the longest consecutive sequence of a given nucleotide in a DNA sequence, while the second example finds the most frequent k-mer within the DNA sequence. Greedy algorithms are powerful tools for solving sequence search and optimization problems, making locally optimal choices to construct globally optimal solutions. Depending on the problem and its constraints, you can adapt and apply similar greedy strategies to tackle various sequence-related challenges.