Very close, except for a few little mistakes: "(\Q$_)" must be "(\Q$_\E)", or else the closing paren will be escaped. But you don't want parens there anyway, it has to be one single capture group: my $rx =  qr/(@{[ join '|', map quotemeta, keys %m_info ]})/; Another, significantly more involved method that I first came up with when I encountered such a problem:

my $rx =  qr/@{ [ join '|', map "(\Q$_->[0]\E)", @m_info ] }/;

for my $record (@data) {
    if (my @match = $record->[1] =~ $regex) {
        my ($m) = grep defined $match[$_], 0 .. $#match;
        $record->[1] = join "_", $m_info[$m]->[3], $m_info[$m]->[1];
    }
}
[download]

The hash method is definitely preferrable though. Reasons to choose one over the other: a large @m_info will take less memory, a large %m_info will provide much faster lookups than the grep loop. So long as memory is not a constraint, the hash is the better choice as the code is both faster and more readable.

Makeshifts last the longest.