快速算法,用于检查Perl中大(x,y)坐标中一对数的成员关系

Question

我有一个排序坐标列表(让我们称之为xycord.txt),如下所示:

chr1    10003486        10043713
chr1    10003507        10043106
chr2    10003486        10043713
chr2    10003507        10043162
chr2    10003532        10042759

实际上,这个文件非常大,有10 ^ 7行.

我想要做的是给出另一个两点坐标,我想检查它们是否落在xycord.txt文件中的任何坐标之间.

我目前的方法是超级慢.因为对于这个大xycord.txt文件还有许多其他两点坐标.

有快速的方法吗？

#!/usr/bin/perl -w

my $point_to_check_x = $ARGV[0] || '10003488';
my $point_to_check_y = $ARGV[1] || '10003489';
my $chrid = $ARGV[2] || "chr1";

my %allxycordwithchr;   
# skip file opening construct
while (<XYCORD_FILE>) {
  my ($chr,$tx,$ty) = split(/\s+/,$_);
  push @{$allxycordwithchr{$chr}},$tx."-".$ty;
}


 my @chosenchr_cord = @{$allxycordwithchr{$chrid}};

 for my $chro_cords (@chosenchr_cord){

  my ($repox,$repoy) = split("-",$chro_cord);
   my $stat = is_in_xycoordsfile($repox,$repoy,$point_to_check_x,$point_to_check_y);
   if ($stat eq "IN"){
      print "IN\n";
   }
 }

sub is_in_xycoordsfile  {

    my      ($x,$y,$xp,$yp) = @_;  
    if ( $xp >= $x && $yp <= $y ) {
        return "IN";
    }
    else {
        return "OUT";
    }

}

更新:我为纠正此事表示歉意.在我之前的帖子中,我过分简化了问题.

实际上,还有一个查询字段(例如染色体名称).因此DB/RB-trees/SQL方法在这个问题上可能是不可行的？

Answer 1

一些建议:

1. 您可以将数据存储在数据库中,例如MySQL或SQLite.然后,您可以使用一个简单的请求,例如:

   "SELECT * FROM coordinates WHERE x<"+xp+" AND y>"+yp
   

   如果你有x和y的索引,这应该是超快的.

2. 你也可以看看R-Trees.几年前我用R树来存储成千上万的城市坐标,我可以在几分之一秒内找到距离给定点最近的城市.在你的例子中,你存储1D范围,但我很确定R树也可以正常工作.您可以在这里找到Perl的R-tree实现.或者您可以使用RectanglesContainingDot,它似乎可以满足您的需求.

3. 您可以在内存中缓存坐标:每个数字看起来需要4个字节来存储,因此如果您有10 ^ 7对数字,这将导致大约80 MB的内存使用量.这就是firefox在我的机器上使用的!当然,如果你这样做,你需要运行某种守护进程,以避免每次需要检查坐标时重新加载整个文件.

4. 您可以混合解决方案2和3.

我倾向于解决方案1:它具有良好的效率/复杂度比率.

Answer 2

除了乌迪Pasmon的好建议,你也可以同时在大文件转换为DBM,然后绑在DBM文件的哈希,便于查找窗口.

转换文件:

#!/usr/bin/perl

use strict;
use warnings;

use DB_File;

my $dbfile = "coords.db";

tie my %coords, "DB_File", $dbfile
    or die "could not open $dbfile: $!";

while (<>) {
    my ($x, $y) = split;
    $coords{"$x-$y"} = 1;
}

检查参数是否是文件的成员:

#!/usr/bin/perl

use strict;
use warnings;

use DB_file;

my ($x, $y) = @ARGV;

tie my %coords, "DB_File", "coords.db"
    or die "could not open coords.db: $!";

print "IN\n" if $coords{"$x-$y"};