Like everyone says--whenever you need to do a lookup in Perl: Think hashes,

#! perl -slw
use strict;
use Data::Dumper;

my @gene_score = (
         [ "gene_name_0", "score_0" ],
         [ "gene_name_1", "score_1" ],
#            ...
         [ "gene_name_400", "score_400" ]
);

my @gene_start_stop_chr = (
         [ "gene_name_0", "start_0", "stop_0", "chr_0" ],
         [ "gene_name_1", "start_1", "stop_1", "chr_1" ],
#            ...
          [ "gene_name_400", "start_400", "stop_400", "chr_400" ],
          [ "gene_name_30000", "start_30000", "stop_30000", "chr_30000
+" ]
);

## Build a hash from the lookup array
my %gene_start_stop_chr = map{ 
    $_->[ 0 ] => [ @{ $_ }[ 1 .. 3 ] ] 
} @gene_start_stop_chr;

## Use it to map the inputs to results
my @results = map{
    [ 
        $_->[ 0 ], 
        $_->[ 1 ], 
        @{ $gene_start_stop_chr{ $_->[ 0 ] } } 
    ]
} @gene_score;

print Dumper \@results;
__END__
P:\test>377857
$VAR1 = [
          [
            'gene_name_0',
            'score_0',
            'start_0',
            'stop_0',
            'chr_0'
          ],
          [
            'gene_name_1',
            'score_1',
            'start_1',
            'stop_1',
            'chr_1'
          ],
          [
            'gene_name_400',
            'score_400',
            'start_400',
            'stop_400',
            'chr_400'
          ]
        ];
[download]