前面讲到了如何用笨方法进行字符串搜索，也讲了如何构建bwt索引，和把bwt索引还原成字符串！

原始字符串是ATGCGTANNGTC

排序过程是下面的

$ATGCGTANNGTC 12

ANNGTC$ATGCGT 6

ATGCGTANNGTC$ 0

C$ATGCGTANNGT 11

CGTANNGTC$ATG 3

GCGTANNGTC$AT 2

GTANNGTC$ATGC 4

GTC$ATGCGTANN 9

NGTC$ATGCGTAN 8

NNGTC$ATGCGTA 7

TANNGTC$ATGCG 5

TC$ATGCGTANNG 10

TGCGTANNGTC$A 1

现在讲讲如何根据bwt索引构建tally，并且用tally搜索方法来搜索字符串！

首先是bwt索引转换为tally

C 12

T 6

$ 0

T 11

G 3

T 2

C 4

N 9

N 8

A 7

G 5

G 10

A 1

这个其实非常简单的，tally就是增加四列计数的列即可

[perl]

$hash_count{'A'}=0;

$hash_count{'C'}=0;

$hash_count{'G'}=0;

$hash_count{'T'}=0;

open FH ,"<$ARGV[0]";

while(<FH>){

        chomp;

@F=split;

$last=$F[0]; # 读取上面的tally文件，分列，判断第一列，并计数

        $hash_count{$last}++;

   print  "$_\t$hash_count{'A'}\t$hash_count{'C'}\t$hash_count{'G'}\t$hash_count{'T'}\n";

}

[/perl]

输出的tally如下

C 12 0 1 0 0

T 6 0 1 0 1

$ 0 0 1 0 1

T 11 0 1 0 2

G 3 0 1 1 2

T 2 0 1 1 3

C 4 0 2 1 3

N 9 0 2 1 3

N 8 0 2 1 3

A 7 1 2 1 3

G 5 1 2 2 3

G 10 1 2 3 3

A 1 2 2 3 3

接下来就是针对这个tally的查询函数了