If you are searching for an exact substring, using index might be faster than using a regex.

Also, your sample input here doesn't show the > character at the beginning of the first line, but the post at StackOveflow does (It also seems you concatenated the first and second line here). You can use it to separate the records as it doesn't appear anywhere else:

#! /usr/bin/perl
use strict;
use warnings;
use feature qw{ say };

open my $in, '<', shift or die $!;

local $/ = '>';
while (my $record = <$in>) {
    next if '>' eq $record;  # Skip the "0th empty record".

    my ($header, $data) = split /\n/, $record, 2;
    $data =~ s/\n//g;
    say "Found in $header" if -1 != index $data, 'CDECGKEFSQGAHLQTHQKV
+H';
}
[download]