Efficient Protein Motif Detection

HardPython

Problem

Genentech's protein analysis pipelines need to identify short sequence motifs shared across multiple candidate proteins. Given a collection of protein sequences, find every contiguous motif of length k that occurs in at least min_sequences distinct sequences.

Count each motif at most once per sequence, even if it appears multiple times within that sequence. Return the motifs in lexicographic order.

Formal Specification

Implement find_common_motifs(sequences, k, min_sequences), where sequences is a list of uppercase protein sequences, k is the motif length, and min_sequences is the minimum number of distinct input sequences that must contain a motif. Return a list of strings.

Example 1: sequences = ["MOTIF", "AMOTIF", "XXMOTIF"], k = 3, min_sequences = 2 returns ["MOT", "OTI", "TIF"], because each motif appears in at least two sequences.

Example 2: sequences = ["AAAA", "AAAT", "AAGA"], k = 2, min_sequences = 2 returns ["AA"]. Repeated occurrences of AA within AAAA count only once for that sequence.

Constraints

1 <= len(sequences) <= 10^4
1 <= k <= 100
k <= len(sequence) <= 10^5
The total number of input characters is at most 10^6
1 <= min_sequences <= len(sequences)
Sequences contain uppercase alphabetic characters only

Function Signature

def find_common_motifs(sequences, k, min_sequences):

Count each motif at most once per sequence, even if it appears multiple times within that sequence. Return the motifs in lexicographic order.

Formal Specification

Example 1: sequences = ["MOTIF", "AMOTIF", "XXMOTIF"], k = 3, min_sequences = 2 returns ["MOT", "OTI", "TIF"], because each motif appears in at least two sequences.

Example 2: sequences = ["AAAA", "AAAT", "AAGA"], k = 2, min_sequences = 2 returns ["AA"]. Repeated occurrences of AA within AAAA count only once for that sequence.