A peptide’s amino acid sequence affects its taste, but how? A rigorous structure–property connection is challenging to determine because of both the exponentially growing peptide sequence space and the scarcity of experimental measurements compared to the size of that space. By sensory methods, many peptides have been identified as tasting bitter or umami. Baselines have been determined but relate only single amino acid characteristics, in particular hydrophobicity in bitter peptides and negative charges for umami. In this work, we refine this picture by extracting sequential amino acid patterns. Our method coarse-grains the peptide sequence space to facilitate the systematic identification of common residue patterns. We identify optimal patterns for both bitter and umami peptides: one hydrophobic followed by four polar residues and two negative followed by three polar residues, respectively. We find systematic improvements compared to both random and the baselines mentioned above. Our method complements quantitative structure–activity relationship methods by leveraging sequential information to help locate taste-specific characteristics in peptides and proteins.