"Is hashes the way to go?"

Your choice of data structure will depend on a number of factors, such as how you want to store and retrieve the structure, how you want to access the data in the structure, and so on. Have a read of "Perl Data Structures Cookbook" to get an idea of what's available.

Here's one possible way:

#!/usr/bin/env perl

use strict;
use warnings;

my %data;

{
    local $/ = "\n>";

    while (<DATA>) {
        $_ = substr $_, 1 if $. == 1;
        my ($ids, $seq, $lab) = split /\n/;
        my ($id1, $id2) = split /[|]/, $ids;
        push @{$data{"$id2-$seq"}}, [$id1, $lab];
    }
}

# For DEMO
use Data::Dump;
dd \%data;

__DATA__
>4kt0_M|P72986
MALSDTQILAALVVALLPAFLAFRLSTELYK
iiiiiiiiiMMMMMMMMMMMMMMMMMIIIII
>6uzv_m|P72986
MALSDTQILAALVVALLPAFLAFRLSTELYK
iiiiiiiiiiiiMMMMMMMMMMMMMMMMMII
>5oy0_m|P72986
MALSDTQILAALVVALLPAFLAFRLSTELYK
iiiiiiiiiMMMMMMMMMMMMMMMMMIIIII
>6hqb_M|P72986
MALSDTQILAALVVALLPAFLAFRLSTELYK
iiiiiiiiiiiMMMMMMMMMMMMMMIIIIII
[download]

Output:

{
  "P72986-MALSDTQILAALVVALLPAFLAFRLSTELYK" => [
    ["4kt0_M", "iiiiiiiiiMMMMMMMMMMMMMMMMMIIIII"],
    ["6uzv_m", "iiiiiiiiiiiiMMMMMMMMMMMMMMMMMII"],
    ["5oy0_m", "iiiiiiiiiMMMMMMMMMMMMMMMMMIIIII"],
    ["6hqb_M", "iiiiiiiiiiiMMMMMMMMMMMMMMIIIIII"],
  ],
}
[download]