Try this:

#! perl -slw
use strict;

local $/ = "\n>";

while( <DATA> ) {
    chomp;
    my( $label, $data ) = m[\A>?(.*?)\n(.*)$]sm;
    $data =~ tr[\n][]d;
    printf "%20s : %s\n", $label, $data;
}
=Output

P:\test>junk3
            Record 1 : AGTCTAGTCATCATCATAAGATCATCAATCACA
      Other Record 1 : ATGAACAGCAGATGAAGAATGGATAG
            Record 2 : AGTCTAGTCATCATCATAAGATCATCAATCACA
      Other Record 2 : ATGAACAGCAGATGAAGAATGGATAG


=cut

__DATA__
>Record 1
AGTCTAGTCAT
CATCATAAGAT
CATCAATCACA
>Other Record 1
ATGAACAGCAG
ATGAAGAATGG
ATAG
>Record 2
AGTCTAGTCAT
CATCATAAGAT
CATCAATCACA
>Other Record 2
ATGAACAGCAG
ATGAAGAATGG
ATAG
[download]