views:

55

answers:

3

I would like to write a Perl function that gets a GFF3 filename and a range (i.e. 100000 .. 2000000). and returns a reference to an array containing all names/accessions of genes found in this range.

I guess using bioperl will make sense, but I have very little experience with it. I can write a script that parses a GFF3 by my self, but if using bioperl (or another packagae) is not too complicated - I'd rather reuse their code.

+2  A: 

You do want to use BioPerl for this, using possibly the Bio::Tools::GFF module.

You should really ask on the BioPerl mailing list. It's very friendly and the subscribers are very knowledgeable -- they'll definitely be able to help you. And once you do get an answer (and if you don't get one here first), I suggest answering your own question here with the answer so we can all benefit!

CanSpice
+1  A: 
use Bio::Tools::GFF;

my $range_start = 100000;
my $range_end   = 200000;

my @features_in_range = ( );


my $gffio = Bio::Tools::GFF->new(-file => $gff_file, -gff_version => 3);

while (my $feature = $gffio->next_feature()) {

    ## What about features that are not contained within the coordinate range but
    ## do overlap it?  Such features             
    if (
        ($feature->start() >= $range_start)
        &&
        ($feature->end()   <= $range_end)
       ) {

        push @features_in_range, $feature;

    }

}

$gffio->close();

DISCLAIMER: Naive implementation. I just banged that out, it's had no testing. I won't even guarantee it compiles.

Mark Johnson
A: 

The following function takes a hash of targets and ranges and returns a function that will iterate over all targets that overlap any of the ranges. The targets should be a reference to an array of references:

my $targets =    
[
  [
    $start,
    $end,
  ],
  ...,
]

The ranges should be a reference to an array of hashes:

my $ranges =
[
  {
    seqname   => $seqname,
    source    => $source,
    feature   => $feature,
    start     => $start,
    end       => $end,
    score     => $score,
    strand    => $strand,
    frame     => $frame,
    attribute => $attribute,
  },
  ...,
]

You can, of course, just pass a single target.

my $brs_iterator
= binary_range_search( targets => $targets, ranges => $ranges );

while ( my $gff_line = $brs_iterator->() ) {
   # do stuff
}

sub binary_range_search {
    my %options = @_;

    my $targets = $options{targets}  || croak 'Need a targets parameter';
    my $ranges  = $options{ranges} || croak 'Need a ranges parameter';

    my ( $low, $high ) = ( 0, $#{$ranges} );
    my @iterators = ();

TARGET:
    for my $range (@$targets) {

    RANGE_CHECK:
        while ( $low <= $high ) {

            my $try = int( ( $low + $high ) / 2 );

            $low = $try + 1, next RANGE_CHECK
                if $ranges->[$try]{end} < $range->[0];
            $high = $try - 1, next RANGE_CHECK
                if $ranges->[$try]{start} > $range->[1];

            my ( $down, $up ) = ($try) x 2;
            my %seen = ();

            my $brs_iterator = sub {

                if (    $ranges->[ $up + 1 ]{end} >= $range->[0]
                    and $ranges->[ $up + 1 ]{start} <= $range->[1]
                    and !exists $seen{ $up + 1 } )
                {
                    $seen{ $up + 1 } = undef;
                    return $ranges->[ ++$up ];
                }
                elsif ( $ranges->[ $down - 1 ]{end} >= $range->[0]
                    and $ranges->[ $down - 1 ]{start} <= $range->[1]
                    and !exists $seen{ $down - 1 }
                    and $down > 0 )
                {
                    $seen{ $down - 1 } = undef;
                    return $ranges->[ --$down ];
                }
                elsif ( !exists $seen{$try} ) {
                    $seen{$try} = undef;
                    return $ranges->[$try];
                }
                else {
                    return;
                }
            };
            push @iterators, $brs_iterator;
            next TARGET;
        }
    }

# In scalar context return master iterator that iterates over the list of range iterators.
# In list context returns a list of range iterators.
    return wantarray
        ? @iterators
        : sub {
        while (@iterators) {
            if ( my $range = $iterators[0]->() ) {
                return $range;
            }
            shift @iterators;
        }
        return;
        };
}
Pedro Silva