BACKGROUND
the history of bioinformatics has been dominated by the search for faster sequence alignment methods.
beginning with dynamic programming for protein and genome sequence alignment, many algorithms have been proposed.
hash tables are used in the series of fasta programs  <cit> , which calculate approximate alignments in shorter times than dynamic programming can.
blast tools, using automatons in their algorithms, are the most famous and most used alignment tools  <cit> .
these tools are fast enough to align expression sequence tags generated by capillary electrophoresis-based dna sequencers to target genomes.
the emergence of next-generation sequencing technology has changed the demands for alignment speed.
a so-called next-generation sequencer can read far more base pairs than a conventional sequencer: more than two billion short dna sequences in a single run.
for such a large number of the sequences, blast tools are too slow to map the sequences to target genomes.
therefore, researchers have called for a faster approach that is focused on mapping short fragments.
to meet this demand, more than  <dig> software programs designed for mapping short dna sequences onto genomes have been developed.
these are classified into two categories according to their algorithms, which are either hash-based or suffix array/burrow–wheeler transition -based  <cit> , maq  <cit>  and soapv <dig>  <cit>  are two hash-based algorithms.
the former indexes short dna sequences and the latter indexes genome sequences.
mrsfast is the one of the newest algorithms that indexes both the short dna sequences and the genome sequences  <cit> .
the first genome-mapping algorithm based on suffix arrays was proposed in  <dig>  <cit>  and implemented as vmatch.
currently, a bwt-based algorithm is the fastest and is used in four tools: bowtie  <cit> , bwa  <cit> , soapv <dig>  <cit> , and segemehl  <cit> .
these algorithms are effective for mapping short sequences to genome positions of perfect matches and one-base mismatches, but are inefficient for mapping to positions for two or more-base mismatches.
in general, they require o computation time to calculate n-base mismatches.
but genome mapping that allows only one-base mismatches is inadequate.
in practice,  <dig> to 40% of short sequences cannot be mapped to the genome.
therefore, “wet” researchers require faster algorithms for mapping short sequences to genome positions with two or more-base mismatches.
in this paper, we propose a method that can accelerate hash-based genome mapping by reducing the number of hash references without increasing the size of the hash table.
in the proposed method, dna subsequences are divided into equivalence classes by using a perfect hamming code.
each equivalence class includes subsequences whose corresponding words on gf are encoded to the corresponding code word of the perfect hamming code.
the code word is used as a hash key to store these subsequences in a hash table.
a perfect hamming code is a special case of a hamming code, known in the field of coding theory  <cit> , that satisfies the hamming bound with equality.
perfect hamming codes have been applied to n-gram analysis of genome sequence  <cit>  and multiple alignment  <cit> .
hash-based genome-mapping algorithms use hash tables.
a hash table is an array indexed by hash values generated from hash keys.
thus, a hash table is an implementation of an associative array.
there are two methods for mapping short reads onto genomes using hash tables.
one is to store subsequences of the genome and their positions in a hash table and the other is to store subsequences of short reads.
as there is no essential difference between their hash usages, we use the former method for the following explanation.
the hash-based methods prepare a hash table whose keys and values represent subsequences of length l cut from a target genome and the subsequence genome positions, respectively.
to map a short sequence to the genome, a sequence is cut into lengths l, and these are used as keys to refer to the hash table.
the methods can find the genome position of a perfect match if the hash table returns at least one entry.
in general, when the lengths of short sequences are longer than the length of the hash key, the methods expand the area of alignment from the genome position.
the differences between methods are how and when they refer to the hash table.
there are three methods to find the n-mismatch genome positions of a subsequence of length l with the hash table.
<dig>  refer to all n-mismatch subsequences.
prepare a hash table whose key length is l, and use the subsequence and its n-mismatch subsequences as keys to refer to the table.
it requires  hash references to find all the n-mismatch genome positions.
<dig>  store n-mismatch positions in the hash table.
for each position of the subsequence of the genome, store the position  times.
the hash keys are the subsequence and its n-mismatch subsequences.
<dig>  use pigeonhole principle; combine hash table and another method.
generate a hash table whose key length is ⌊l/n⌋.
after getting the perfect-match genome position of length ⌊l/n⌋ by referring to the hash table, find n-mismatch sequences by another method, such as dynamic programming or bwt.
these methods are effective when l is small and n equals  <dig>  but they are difficult to use when n is  <dig> or more because the number of 2-mismatch sequences of length l is l/ <dig> ∗  <dig> and that of 3-mismatches is l/ <dig> ∗  <dig>  the first and second methods require too many hash references and too big a hash table, respectively.
the third method is the best, but as n becomes larger, the ability to narrow the genome position down becomes weaker, and so the load of the post process to find n-mismatch sequences increases.
to overcome these difficulties and improve the effectiveness of using hash tables for genome mapping, technical breakthroughs are needed.
we propose a method to reduce the number of hash references to find the genome positions of  <dig> or more mismatches without enlarging the size of the hash table.
to realize the method, 4-ary perfect hamming code is used.
RESULTS
perfect hamming codes as hash keys
idea
we first describe the main idea of the proposed method.
we define a graph whose nodes are all the subsequences of length l and edges are between pairs of subsequences of one nucleotide difference.
the graph has 4l nodes and each node has 3l edges.
assume we divide the 4l nodes of the graph into 4l/ equivalence classes such that each class has a center node and 3l adjacent nodes.
then, we use the center node as the hash key to store the genome positions of 3l +  <dig> subsequences in a hash table.
for example, figure  <dig> shows a part of the graph of length  <dig>  the node “aaaaa” has  <dig> adjacent nodes.
these comprise an equivalence class with subsequence“aaaaa” at its center.
to store “acaaa”, which belongs to the equivalence class, the center word “aaaaa” is used as a hash key.
the features of this hash table are as follows:  the number of entries in the hash table does not increase because each subsequence is stored only once.
using this hash table, we can reduce the number of hash references to find the genome positions of subsequences of  <dig> or more-mismatches.
we explain the concept how to reduce the number of hash references to find 1-mismatches by using an example.
let the length of subsequence be  <dig>  the hash table be as described above, and s be a subsequence for which we want to find the entries of 1-mismatch.
there are  <dig> 1-mismatch subsequences to be referred to.
when s is the center subsequence of the equivalence class, such as “aaaaa” in figure  <dig>  using s as the hash key, one can find all the genome positions of 1-mismatch subsequences.
when s is not the center subsequence of its equivalence class, seven hash keys are needed.
one hash key is the center subsequence of its equivalence class.
this leads to  <dig> of the  <dig> 1-mismatch subsequences.
the rest of  <dig> subsequences are members of six different equivalence classes, and so the center subsequence of these classes are used as the other six keys.
figure  <dig> shows the equivalence class that s=“caaaa” belongs to and an equivalence class containing the two adjacent subsequences “caaat” and “caaga”.
because the proportion of center words  to total words is 1/ <dig>  the expected number of hash references is 1/ <dig> ∗  <dig> + 15/ <dig> ∗  <dig> =  <dig> , which is  <dig> % of the number of exact and 1-mismatch subsequences.
the requirements for the establishment of the equivalence classes need to be determined.
at a minimum, the length of the subsequence l must satisfy the condition:
this shows that 3l +  <dig> must be a power of  <dig>  for example, l =  <dig> and  <dig> satisfies the condition.
it is not clear that the above equation is a sufficient condition for constructing equivalence classes.
even if it is, two problems still remain; how to construct the equivalence classes and how to calculate the center words from a given subsequence.
perfect hamming codes provide solutions to both these problems.
perfect hamming code
a perfect hamming code  is a hamming code that satisfies the equation of the hamming bound,
where c is a set of q–ary block code of length n, d is the minimum hamming distance between code words, and .
in the phc method, all the received words are classified into a code word or a 1-bit error.
in other words, all the words are decoded to code words whose hamming distance is  <dig> or  <dig>
the condition for a q-ary -hamming code be a perfect code is n = qk/.
in the case of a 4-ary code, -hamming code and -hamming code are perfect.
their parity-check matrixes are shown in equations  and , respectively.
where  are the elements in the galois field gf.
to get a code word x from received word z, the syndrome s = ht is used to determine the error vector e =   <cit> .
if the syndrome s is not zero, the column of h that is equal to or constant factor of s indicates the error position of z. the addition and multiplication tables are shown in table  <dig>
the code word is calculated from a received word as follows.
<dig>  calculate the syndrome s.
<dig>  if the syndrome s is zero, then the recieved word is the code word.
<dig>  find a column c of parity-check matrix that is a constant factor t of the syndrome.
<dig>  subtract t from the column c of the received word and the result is the code word.
for example, assume the word z =  is received.
the code word of z is calculated as follows.
the syndrome s of z is:
as st is equal to α <dig> × , which is α <dig> times the fourth column of h, subtract  from z:
the code word of z is .
the -hamming codes are composed of the information digits and the check digits.
the information digits are k arbitrary digits of the code and the other n – k digits are the check digits.
the generator matrix g can reproduce check digits from information digits.
therefore, code words can be uniquely represented by the k digits.
in this paper, we call these representations short codes.
phc and dna subsequence
dna sequences are composed of four nucleotides, adenine, cytosine, guanine and thymine.
let these correspond one-to-one to the elements of galois field gf.
then, dna sequences correspond to words on the galois field.
without loss of generality, let  correspond to .
the sequence “gggta” is expressed as the word , and the word  represents the dna sequence “caaaa”.
this correspondence relationship and the phc enables us to build the equivalence classes described in section idea.
each equivalence class is composed of a dna subsequence that corresponds to a phc code word and dna subsequences whose corresponding words are error-corrected to the code word.
figure  <dig> shows an equivalence class.
the dna subsequence “aaaaa” corresponds to word  on gf and is a code word of 4-ary -phc.
from the properties of phc, all the words whose hamming distances from the code word  are  <dig> are error-corrected to the code word, and they are adjacent nodes of “aaaaa”.
additional file  <dig> shows correspondence table of 5-mer subsequences and code words of 4-ary -phc.
in the following, we regard dna subsequences and their corresponding codes on the galois field as equivalent .
algorithms
we propose a hash table for genome mapping whose hash keys are code words of phc.
then we show its use and efficiency in finding genome positions of n-mismatches and n-gaps.
following is a description of the notation used in this section.
preparing the hash table
there are two ways to construct hash tables for mapping short dna sequences onto a genome.
one uses subsequences of the genome as hash keys to store their genome positions in a hash table.
and another uses subsequences of short dna sequence as the hash key.
because both of these use dna subsequences as hash keys, our method can be applied to either.
in the following, we use the former in the explanation.
the hash table of our method uses the representative subsequence of the equivalence classes as hash keys.
the representative is the code word on phc.
without loss of generality, the information digits of the code words can be used as the hash key.
given an  – phc on g, let s be a set of subsequences of the genome with length l = n. the genome positions of a subsequence s ∈ s are stored in the hash table along with a hash key c or its information digits i).
figure  <dig> shows the use of hash tables.
searching for n-mismatches
in this section we describe how to find genome positions of 1- and 2-mismatch subsequences of a given subsequence s given the hash table prepared as described in section preparing the hash table.
the efficiency of the method is also described.
let s be a dna subsequence.
the set of hash keys k required to refer to all the entries of perfect match and 1– to n–mismatches is naturally expressed as follows.
the number of keys |kn| is less than the number of subsequences to be referred to, .
specifically, when the length of s is  <dig> and  <dig>  the expected number of keys for 1-mismatch k <dig> are  <dig>  and  <dig> , respectively.
as the number of subsequences of perfect and 1-mismatch are  <dig> + 5c <dig> ×  <dig>  the method reduces the number of hash keys to  <dig> %  and  <dig> % , respectively.
we summarize these values in the “ratio” column of table  <dig>  in the following, we analyze the properties of the hash keys k <dig> and k <dig>
∗ <dig> :s always includes one code word.
∗2: neither the first half nor the second half are code words.
the reference formula when one of the two halves is a code word is  <dig> + 30x <dig> + 267x <dig> + 684x <dig> + 810x <dig>  ∗3: neither the first half or second half are code words.
the reference formula when one of the two halves is a code word is  <dig> + 30x <dig> + 42x <dig> + 54x <dig>
first, we analyze k <dig> for s of length  <dig>  the subsequence s is classified into two cases according to whether s is a code word on phc.
case 1: s is a code word.
as s is the code word, all the 1-mismatch words of s are decoded to s by phc.
that is to say, they belong to the same equivalence class e. therefore, s is used as a hash key and it can refer to all the 1-mismatch subsequences.
case 2: s is not a code word.
figure  <dig> shows the fifteen 1-mismatch subsequences.
as s is not a code word, the equivalence class e has three 1-mismatch subsequence of s. one of these three is the code word c. these three differ from s at the same digit.
assume s= “aaaag”.
then, the code word c is “aaaaa”, and the words “aaaac” and “aaaat” belong to same equivalence class, e. these differ at the fifth digit.
the hash key c can refer to four sequences at once.
the rest of  <dig> words belong to six equivalence classes.
assume that word t differs at j-th digit.
t is not a code word because dh) =  <dig> and the distance between code words must be more than  <dig>  the code word c and t differ at the k-th digit, where k ≠ i, j. there is a word u that differs from s at the k-th digit and c at the j-th digit.
because c belongs to the equivalence class e, use c as a hash key and two words t and u can be referred to.
finally, the number of keys k <dig> to refer to all the 1-mismatch subsequences is seven.
because the proportions of case  <dig> and case  <dig> are respectively 1/ <dig> and 15/ <dig>  the expected number of keys in k <dig> is  <dig>  .
next, we show an algorithm to calculate the set of hash keys k <dig>
input : s
output : k <dig> : a set of hash keys
<dig>  k <dig> ← c
<dig>  s := c  and return )
<dig>  for t in n <dig> add c to k1
<dig>  return )
the algorithm calculates code words  <dig> times when s is not a code word, where the number of the hash keys is seven.
there appears to be redundancy.
there are various ways of reducing the computation time of the code words, but it is better not to use complicated algorithms.
the calculation of code words is fast because the operations + and × on g can be calculated as binary operations.
by using the set of hash keys k <dig>  not only the entries of s and all the 1-mismatch subsequences are referred to, but also the other entries are.
for example, when s is not a code word,  <dig> subsequences of 2-mismatch belongs to the same equivalence class e. therefore, the hash key c  refers to these subsequences.
to analyze the properties of these subsequences, we define a reference formula:
where s is a subsequence, k is a set of hash keys, and the coefficient a represents the number of subsequences that are referred to by k and whose distance from s is b.
for case  <dig>  because s is the code word, all the 1-mismatch subsequences belong to e. therefore, the reference formula for case  <dig> is:
for case  <dig>  there are  <dig> hash keys in k <dig>  because the equivalence class of c  has  <dig> 2-mismatch subsequences, the reference formula of c  is:
each of the equivalence classes of the other hash keys has two 1-mismatch sequences, five 2-mismatch sequences and nine 3-mismatch sequences.
the reference formula of k <dig> – {c} is:
finally, the reference formula for the case  <dig> is:
the reference formula shows the proposed method searches many 2- and 3-mismatch sequences.
we discuss this feature in section discussion.
the above algorithm and analysis can be applied to the word length  <dig>  the numbers of hash keys are  <dig> and  <dig> for case  <dig> and case  <dig>  respectively.
using the rate of occurrences of case  <dig> and case  <dig>  1/ <dig> and 63/ <dig>  respectively, the expected number of hash keys is  <dig> .
the reference formulas are shows in table  <dig>
to refer to all the entries of 2-mismatches, our method requires  <dig>  hash keys, which is  <dig> % of the number of subsequences with  <dig> or fewer mismatches.
when the length of subsequences is  <dig>  figure  <dig> shows the subsequence s and its surroundings when s is a code word.
the number of subsequences of exact 2-mismatches |n2| is  <dig>  and the elements of |n2| are neighbors of n <dig>  each n ∈ n <dig> has two neighbors of n <dig> and each n belongs to an equivalence class that contains other two elements of n <dig>  in other words,  <dig> equivalence classes are required to cover n <dig>  in total, the number of required keys k <dig> is  <dig>  the reference formula is:
in case  <dig>  s is not a code word and figure  <dig> shows 2-mismatch sequences of s. the equivalence classes 2-mismatch subsequences belong to are classified into four types.
type 1: 2-mismatch subssequences belong to this type are neighbors of c.
type 2: for some t such that dh =  <dig> and c ≠ c, 2-mismatch subsequences are neighbors of t belonging to c.
type 3: for some t such that dh =  <dig> and c ≠ c, they are neighbors of t not belonging to c.
type 4: for some u such that dh =  <dig> and c = c, they are neighbors of u not belonging to c.
types  <dig> and  <dig> are included in k <dig> and the numbers of subsequences are  <dig> and  <dig>  respectively.
the equivalence classes of type  <dig> are the right-most circles in figure  <dig>  similar to subsequences of 2-mismatches in figure  <dig>  three 2-mismatch subsequences belong to each equivalence class.
the number of equivalence classes is eight and they includes  <dig> 2-mismatch subsequences.
the bottom-left circle in figure  <dig> represents type  <dig>  the relation between of types  <dig> and  <dig> looks similar to that between types  <dig> and  <dig>  in fact, type  <dig> is a union of k <dig> – c for over each possible u. as the size of u is  <dig>  type  <dig> has  <dig> equivalence classes.
in total, the number of hash keys to refer to 2-mismatch subsequences is  <dig> .
the reference formula is as follows:
in the same manner, we can analyze the hash keys k <dig> for the subsequence of length of  <dig>  in this case, the reference formula when s = c becomes:
and the formula when s ≠ c is:
search n-gaps
to align dna subsequence and a genome, there are three types of gaps.
these are gaps in short dna sequence, gaps in genome sequence, and gaps in both.
our method can reduce the number of hash keys to refer to gaps in short dna sequences.
given a subsequence with gaps s, hash keys to refer to the genome positions are a set of code words of subsequences which with the gaps of s are substituted with nucleotides.
the expected numbers of hash keys are  <dig>  and  <dig>  when the length of a subsequence with one gap is  <dig> and  <dig> respectively.
let s be a subsequence with one-gap, such as “aa-aa”, and s be a set of subsequences for which a gap in s is substituted with a nucleotide, in this case the set comprising “aaaaa”, “aacaa”, “aagaa”, and “aataa”.
to find the genome position that matches s, we need to refer to entries that correspond to s.
when a subsequence t ∈ s is a code word, all the subsequences in s belong to the same equivalence class.
therefore, by using c as a hash key, all the entries correspond to gapped subsequence s can be referred to from.
in this case, the reference formula becomes  <dig> + 12x, where the index number of x represents the minimum distance from the four subsequences in s.
if no t ∈ s is a code word, the four subsequences belong to different equivalence classes.
therefore, four hash keys are required and the reference formula is  <dig> + 60x.
the proportion for which one member of s is a code word is |s|/# of words in a equivalence class = 4/ <dig> = 1/ <dig>  and so the expected number of hash keys is .
in the same way, when the length is  <dig>  the expected number of hash keys is .
the reference formulas are shown in table  <dig>
next, we consider a subsequence with two gaps.
let s be a subsequence of length  <dig> with two gaps such as “a-a-a” and s be the set of  <dig> sequences for which the gaps in s are replaced with nucleotides.
the number of information digits in -phc is  <dig>  and so one of  <dig> words in s is a code word t. the code word t is the only code word in s because the maximum hamming distance among words in s is  <dig>  which equals the number of gaps, and the minimum hamming distance between code words is  <dig>  the equivalence class e includes seven subsequences of s; let u be the remaining subsequences ).
because u ∈ u is not a code word and dh =  <dig>  the distance between t and the code word c is  <dig> ,t) = 3).
this implies that c and t differ at a non-gapped position in t. therefore, for all u, v ∈ u, u ≠ v and d, v) = d +  <dig> ≥  <dig>  thus, all the subsequences in u belong to different equivalence classes and nine  hash keys are required to refer to 2-gap subsequences.
for example, if s=“a-a-a”, s includes a code word t =“aaaaa” and t can refer to  <dig> sequences: “aaaaa”, “acaaa”, “agaaa”, “ataaa”, “aaaca”, “aaaga”, and “aaata”.
the set of remaining subsequences are u = {“acaca”, “acaga”, “acata”, “agaca”, “agaga”, “agata”, “ataca”, “ataga”, “ataga” }.
let u ∈ u = “acaca”.
the code cord c is “acacc” and hamming distance from the rest of u are two or three.
therefore, all subsequences in u belong to different equivalence classes.
length of subsequence
the code length of the phc is restricted to  <dig> or  <dig> in practice.
this is inconvenient.
therefore, we next explain ways to elongate the code length.
there are four ways to elongate the code length.
the first way is to simply add nucleotides before or/and after the code words.
two other ways are serialization and parallelization of phcs.
the former method serializes more than two phcs and serialized code words are used as the hash key.
the latter one uses more than two hash tables for the parallelization and is a way to utilize the pigeonhole principle where pigeons are mismatches or gaps and holes are the regions without mismatches and gaps.
the fourth way is a combination of the three.
figure  <dig> shows the concepts behind each.
in the following, we show a serialized code and a parallelized code, both of length  <dig>
let s = s1s <dig> be a sequence of length  <dig> and s <dig> and s <dig> be the subsequences of length  <dig>  the hash key used in the serialization to store s is cc.
in this case, each equivalence class holds  <dig> subsequences.
to refer to the entry of a sequence s = s1s <dig> and the  <dig> 1-mismatch sequences, the set of hash keys is:
and the expected number of hash keys is  <dig> .
to prove this, we consider four cases:
case  <dig> s <dig> and s <dig> are both code words.
case  <dig> s <dig> is a code word, but s <dig> is not.
case  <dig> s <dig> is a code word, but s <dig> is not.
case  <dig> neither s <dig> nor s <dig> is a code word.
in case  <dig>  use s1s <dig> as a hash key; this can refer to all the 1-mismatches.
the reference formula in this case is the square of the reference formula of length  <dig>   =  <dig> + 30x + 225x <dig>
in case  <dig>  we need to consider two subcases based on the position of the 1-mismatch.
when the position is in the first half of s, the hash key s1s <dig> can refer to all of them.
when the position is in the second half, the second half of the hash keys becomes one of the seven words in k <dig>  therefore, a set of hash keys is:
because s <dig> ∈ k <dig>  the hash keys in the second subcase include the hash keys in the first subcase.
therefore, the number of hash keys |k1| is  <dig>  the reference formula is:
in case  <dig>  similar to in case <dig>  the set of hash keys is:
and the reference formula is same as that of case  <dig>
in case  <dig>  the set of hash keys is the union of {s1t|t ∈ k1} and {ts2|t ∈ k1}, which correspond to 1-mismatch in the first half and 1-mismatch in the second half, respectively.
because both of these include cc, the number of hash keys is  <dig> .
the reference formula is:
the proportions of cases  <dig> through  <dig> of 1/ <dig>  15/ <dig>  15/ <dig>  and 225/ <dig>  respectively, and so the expected number of hash keys is  <dig> .
the parallelization requires two hash tables and each subsequence is stored in both hash tables.
therefore, the total size of the hash tables is twice that of serialization.
the hash keys are cs2: the first haf is phc, and s1c: the second half is phc.
consequently, two types of equivalence classes are used in the parallelization and each equivalence class holds  <dig> subsequences.
the set of hash keys for 1-mismatch sequences is:
where each set corresponds to one of the two hash tables.
the expectation number of keys is  <dig> .
let us consider the four cases, which are the same as those for serialization.
in case  <dig>  use s1s <dig> as the hash key for two hash tables and all the entries of 1-mismatch are referred to.
in this case, the reference formula is  +  –  <dig> =  <dig> + 30x.
as a subsequence s1s <dig> is stored in both hash tables, one is subtracted in the formula.
though the number of hash keys appears to be one, it is used twice.
thus the number of hash keys |k1| is two.
in case  <dig>  the hash keys are:
the total number hash keys is  <dig> and the reference formula is:
case  <dig> is similar to case  <dig>  in this case the hash keys are:
in case  <dig>  the hash keys when the first half includes the mismatch are {ts2|t ∈ k1} and that for the second half are {s1t|t ∈ k1}.
the number of hash keys is  <dig> and the reference formula is:
the proportions of the cases are same as for serialization, and the expected number of hash keys is  <dig> .
discussion
to search genome positions of n-mismatches and n-gaps with our method, table  <dig> shows it also searches some positions of n+α-mismatch.
for example, our method searches not only  <dig> perfect match and  <dig> 1-mismatch subsequences, but also  <dig> 2-mismatches and  <dig> 3-mismatches as byproducts  <dig> % and  <dig> % of all 2- and 3-mismatches, respectively.
this proportion increases to  <dig> %, 20%  when l =  <dig>  these byproducts are, in fact, effective.
one reason for the current low mapping ratios from dna sequencers of short reads to a genome is the small number of mismatches and gaps that the employed mapping method can find.
therefore, increasing the numbers of mismatches and gaps will contribute to increasing the mapping ratio and subsequent biological analyses, even if the method is probabilistic.
the increasing demand to map massive amounts of short dna sequences to genomes is inevitable.
because the number of short sequences is enormous, it is difficult to ensure finding all genome positions of 1-mismatches in a practical computation time.
therefore, faster methods are required and the proposed method is a step in that direction.
we have shown that the proposed method can reduce the number of keys necessary to find the genome positions of n-mismatches.
the main idea behind the method is to classify the subsequences into equivalence classes using phc.
because equivalence classes contain multiple subsequences, our method can increase the density of the hash table over those using in the usual method.
that is to say, our method can use longer subsequences.
for example, the size of human genome is about 3g bases long.
when this is stored it with subsequences of length  <dig> in usual way, the density of the hash table is  <dig> × 1012/ <dig> ≈  <dig> %.
on the other hand, the hash table using our proposed method using -phc, the density is  <dig> × 1012/ =  <dig> × 1012/ <dig> ≈  <dig> %.
that is to say, our method can use longer subsequences.
the length of subsequence is sensitive to the efficiency of the genome-mapping programs, and the longer the better, for a given density of hash table.
therefore, the proposed method has an advantage from this point of view.
we consider the computation time for code words is far shorter than a hash reference when we describe the effectiveness of the proposed method.
in practice, the calculation of the syndrome using the parity-check matrix of the hamming code is very short, even if on gf, and so it is easy to calculate the code word from a subsequence.
also, the calculation is small enough to be executed within a cpu cache.
on the other hand, the size of hash table is larger than the size of cpu caches.
some exceeds the size of memory because the number of entries is almost equal to the length of the target genome.
the hash reference is apparently slower than the calculation of the code word.
therefore, the advantage of reducing the hash references exceeds the disadvantage of additional tasks to calculate code words.
with these advantages, our method will help to implement faster genome mapping programs.
CONCLUSIONS
the paper shows perfect hamming code can reduce the number of hash references for hash-based genome mapping.
the method encodes subsequences to perfect hamming codes on gf and use them as hash keys.
it can reduce by about 70% the number of hash keys necessary for searching the genome positions of all 2-mismatches of 21-base-long dna subsequence.
as the amount of data that dna sequencers generates continues to increase and more accurate genome mappings are required, our method will help to develop faster genome mapping software.
competing interests
the authors declare that they have no competing interests.
authors' contributions
yt provide the key idea and the mathematical analyses.
ss and hm provide valuable help on the topics.
all authors discusses the results and commented on the manuscript.
supplementary material
additional file 1
dna sequences and their code words.
all the 5-mer dna sequences and their code words on 4-ary -perfect hamming codes.
click here for file
acknowledgements
this work was partially supported by kakenhi  and .
this article has been published as part of bmc genomics volume  <dig> supplement  <dig>  2011: tenth international conference on bioinformatics – first iscb asia joint conference  <dig> : computational biology.
the full contents of the supplement are available online at http://www.biomedcentral.com/1471-2164/12?issue=s <dig>

 the history of bioinformatics has been dominated by the search for faster sequence alignment methods. beginning with dynamic programming for protein and genome sequence alignment, many algorithms have been proposed. hash tables are used in the series of fasta programs, which calculate approximate alignments in shorter times than dynamic programming can. blast tools, using automatons in their algorithms, are the most famous and most used alignment tools. these tools are fast enough to align expression sequence tags generated by capillary electrophoresis-based dna sequencers to target genomes. the emergence of next-generation sequencing technology has changed the demands for alignment speed. a so-called next-generation sequencer can read far more base pairs than a conventional sequencer: more than two billion short dna sequences in a single run. for such a large number of the sequences, blast tools are too slow to map the sequences to target genomes. therefore, researchers have called for a faster approach that is focused on mapping short fragments. to meet this demand, more than software programs designed for mapping short dna sequences onto genomes have been developed. these are classified into two categories according to their algorithms, which are either hash-based or suffix array/burrow–wheeler transition -based, maq and soapv are two hash-based algorithms. the former indexes short dna sequences and the latter indexes genome sequences. mrsfast is the one of the newest algorithms that indexes both the short dna sequences and the genome sequences. the first genome-mapping algorithm based on suffix arrays was proposed in and implemented as vmatch. currently, a bwt-based algorithm is the fastest and is used in four tools: bowtie, bwa, soapv, and segemehl. these algorithms are effective for mapping short sequences to genome positions of perfect matches and one-base mismatches, but are inefficient for mapping to positions for two or more-base mismatches. in general, they require o computation time to calculate n-base mismatches. but genome mapping that allows only one-base mismatches is inadequate. in practice, to 40% of short sequences cannot be mapped to the genome. therefore, “wet” researchers require faster algorithms for mapping short sequences to genome positions with two or more-base mismatches. in this paper, we propose a method that can accelerate hash-based genome mapping by reducing the number of hash references without increasing the size of the hash table. in the proposed method, dna subsequences are divided into equivalence classes by using a perfect hamming code. each equivalence class includes subsequences whose corresponding words on gf are encoded to the corresponding code word of the perfect hamming code. the code word is used as a hash key to store these subsequences in a hash table. a perfect hamming code is a special case of a hamming code, known in the field of coding theory, that satisfies the hamming bound with equality. perfect hamming codes have been applied to n-gram analysis of genome sequence and multiple alignment. hash-based genome-mapping algorithms use hash tables. a hash table is an array indexed by hash values generated from hash keys. thus, a hash table is an implementation of an associative array. there are two methods for mapping short reads onto genomes using hash tables. one is to store subsequences of the genome and their positions in a hash table and the other is to store subsequences of short reads. as there is no essential difference between their hash usages, we use the former method for the following explanation. the hash-based methods prepare a hash table whose keys and values represent subsequences of length l cut from a target genome and the subsequence genome positions, respectively. to map a short sequence to the genome, a sequence is cut into lengths l, and these are used as keys to refer to the hash table. the methods can find the genome position of a perfect match if the hash table returns at least one entry. in general, when the lengths of short sequences are longer than the length of the hash key, the methods expand the area of alignment from the genome position. the differences between methods are how and when they refer to the hash table. there are three methods to find the n-mismatch genome positions of a subsequence of length l with the hash table. refer to all n-mismatch subsequences. prepare a hash table whose key length is l, and use the subsequence and its n-mismatch subsequences as keys to refer to the table. it requires hash references to find all the n-mismatch genome positions. store n-mismatch positions in the hash table. for each position of the subsequence of the genome, store the position times. the hash keys are the subsequence and its n-mismatch subsequences. use pigeonhole principle; combine hash table and another method. generate a hash table whose key length is ⌊l/n⌋. after getting the perfect-match genome position of length ⌊l/n⌋ by referring to the hash table, find n-mismatch sequences by another method, such as dynamic programming or bwt. these methods are effective when l is small and n equals but they are difficult to use when n is or more because the number of 2-mismatch sequences of length l is l/ ∗ and that of 3-mismatches is l/ ∗ the first and second methods require too many hash references and too big a hash table, respectively. the third method is the best, but as n becomes larger, the ability to narrow the genome position down becomes weaker, and so the load of the post process to find n-mismatch sequences increases. to overcome these difficulties and improve the effectiveness of using hash tables for genome mapping, technical breakthroughs are needed. we propose a method to reduce the number of hash references to find the genome positions of or more mismatches without enlarging the size of the hash table. to realize the method, 4-ary perfect hamming code is used.  perfect hamming codes as hash keys idea we first describe the main idea of the proposed method. we define a graph whose nodes are all the subsequences of length l and edges are between pairs of subsequences of one nucleotide difference. the graph has 4l nodes and each node has 3l edges. assume we divide the 4l nodes of the graph into 4l/ equivalence classes such that each class has a center node and 3l adjacent nodes. then, we use the center node as the hash key to store the genome positions of 3l + subsequences in a hash table. for example, figure shows a part of the graph of length the node “aaaaa” has adjacent nodes. these comprise an equivalence class with subsequence“aaaaa” at its center. to store “acaaa”, which belongs to the equivalence class, the center word “aaaaa” is used as a hash key. the features of this hash table are as follows: the number of entries in the hash table does not increase because each subsequence is stored only once. using this hash table, we can reduce the number of hash references to find the genome positions of subsequences of or more-mismatches. we explain the concept how to reduce the number of hash references to find 1-mismatches by using an example. let the length of subsequence be the hash table be as described above, and s be a subsequence for which we want to find the entries of 1-mismatch. there are 1-mismatch subsequences to be referred to. when s is the center subsequence of the equivalence class, such as “aaaaa” in figure using s as the hash key, one can find all the genome positions of 1-mismatch subsequences. when s is not the center subsequence of its equivalence class, seven hash keys are needed. one hash key is the center subsequence of its equivalence class. this leads to of the 1-mismatch subsequences. the rest of subsequences are members of six different equivalence classes, and so the center subsequence of these classes are used as the other six keys. figure shows the equivalence class that s=“caaaa” belongs to and an equivalence class containing the two adjacent subsequences “caaat” and “caaga”. because the proportion of center words to total words is 1/ the expected number of hash references is 1/ ∗ + 15/ ∗ =, which is % of the number of exact and 1-mismatch subsequences. the requirements for the establishment of the equivalence classes need to be determined. at a minimum, the length of the subsequence l must satisfy the condition: this shows that 3l + must be a power of for example, l = and satisfies the condition. it is not clear that the above equation is a sufficient condition for constructing equivalence classes. even if it is, two problems still remain; how to construct the equivalence classes and how to calculate the center words from a given subsequence. perfect hamming codes provide solutions to both these problems. perfect hamming code a perfect hamming code is a hamming code that satisfies the equation of the hamming bound, where c is a set of q–ary block code of length n, d is the minimum hamming distance between code words, and. in the phc method, all the received words are classified into a code word or a 1-bit error. in other words, all the words are decoded to code words whose hamming distance is or the condition for a q-ary -hamming code be a perfect code is n = qk/. in the case of a 4-ary code, -hamming code and -hamming code are perfect. their parity-check matrixes are shown in equations and, respectively. where are the elements in the galois field gf. to get a code word x from received word z, the syndrome s = ht is used to determine the error vector e =. if the syndrome s is not zero, the column of h that is equal to or constant factor of s indicates the error position of z. the addition and multiplication tables are shown in table the code word is calculated from a received word as follows. calculate the syndrome s. if the syndrome s is zero, then the recieved word is the code word. find a column c of parity-check matrix that is a constant factor t of the syndrome. subtract t from the column c of the received word and the result is the code word. for example, assume the word z = is received. the code word of z is calculated as follows. the syndrome s of z is: as st is equal to α ×, which is α times the fourth column of h, subtract from z: the code word of z is. the -hamming codes are composed of the information digits and the check digits. the information digits are k arbitrary digits of the code and the other n – k digits are the check digits. the generator matrix g can reproduce check digits from information digits. therefore, code words can be uniquely represented by the k digits. in this paper, we call these representations short codes. phc and dna subsequence dna sequences are composed of four nucleotides, adenine, cytosine, guanine and thymine. let these correspond one-to-one to the elements of galois field gf. then, dna sequences correspond to words on the galois field. without loss of generality, let correspond to. the sequence “gggta” is expressed as the word, and the word represents the dna sequence “caaaa”. this correspondence relationship and the phc enables us to build the equivalence classes described in section idea. each equivalence class is composed of a dna subsequence that corresponds to a phc code word and dna subsequences whose corresponding words are error-corrected to the code word. figure shows an equivalence class. the dna subsequence “aaaaa” corresponds to word on gf and is a code word of 4-ary -phc. from the properties of phc, all the words whose hamming distances from the code word are are error-corrected to the code word, and they are adjacent nodes of “aaaaa”. additional file shows correspondence table of 5-mer subsequences and code words of 4-ary -phc. in the following, we regard dna subsequences and their corresponding codes on the galois field as equivalent. algorithms we propose a hash table for genome mapping whose hash keys are code words of phc. then we show its use and efficiency in finding genome positions of n-mismatches and n-gaps. following is a description of the notation used in this section. preparing the hash table there are two ways to construct hash tables for mapping short dna sequences onto a genome. one uses subsequences of the genome as hash keys to store their genome positions in a hash table. and another uses subsequences of short dna sequence as the hash key. because both of these use dna subsequences as hash keys, our method can be applied to either. in the following, we use the former in the explanation. the hash table of our method uses the representative subsequence of the equivalence classes as hash keys. the representative is the code word on phc. without loss of generality, the information digits of the code words can be used as the hash key. given an – phc on g, let s be a set of subsequences of the genome with length l = n. the genome positions of a subsequence s ∈ s are stored in the hash table along with a hash key c or its information digits i). figure shows the use of hash tables. searching for n-mismatches in this section we describe how to find genome positions of 1- and 2-mismatch subsequences of a given subsequence s given the hash table prepared as described in section preparing the hash table. the efficiency of the method is also described. let s be a dna subsequence. the set of hash keys k required to refer to all the entries of perfect match and 1– to n–mismatches is naturally expressed as follows. the number of keys |kn| is less than the number of subsequences to be referred to,. specifically, when the length of s is and the expected number of keys for 1-mismatch k are and, respectively. as the number of subsequences of perfect and 1-mismatch are + 5c × the method reduces the number of hash keys to % and %, respectively. we summarize these values in the “ratio” column of table in the following, we analyze the properties of the hash keys k and k ∗:s always includes one code word. ∗2: neither the first half nor the second half are code words. the reference formula when one of the two halves is a code word is + 30x + 267x + 684x + 810x ∗3: neither the first half or second half are code words. the reference formula when one of the two halves is a code word is + 30x + 42x + 54x first, we analyze k for s of length the subsequence s is classified into two cases according to whether s is a code word on phc. case 1: s is a code word. as s is the code word, all the 1-mismatch words of s are decoded to s by phc. that is to say, they belong to the same equivalence class e. therefore, s is used as a hash key and it can refer to all the 1-mismatch subsequences. case 2: s is not a code word. figure shows the fifteen 1-mismatch subsequences. as s is not a code word, the equivalence class e has three 1-mismatch subsequence of s. one of these three is the code word c. these three differ from s at the same digit. assume s= “aaaag”. then, the code word c is “aaaaa”, and the words “aaaac” and “aaaat” belong to same equivalence class, e. these differ at the fifth digit. the hash key c can refer to four sequences at once. the rest of words belong to six equivalence classes. assume that word t differs at j-th digit. t is not a code word because dh) = and the distance between code words must be more than the code word c and t differ at the k-th digit, where k ≠ i, j. there is a word u that differs from s at the k-th digit and c at the j-th digit. because c belongs to the equivalence class e, use c as a hash key and two words t and u can be referred to. finally, the number of keys k to refer to all the 1-mismatch subsequences is seven. because the proportions of case and case are respectively 1/ and 15/ the expected number of keys in k is. next, we show an algorithm to calculate the set of hash keys k input: s output: k: a set of hash keys k ← c s:= c and return ) for t in n add c to k1 return ) the algorithm calculates code words times when s is not a code word, where the number of the hash keys is seven. there appears to be redundancy. there are various ways of reducing the computation time of the code words, but it is better not to use complicated algorithms. the calculation of code words is fast because the operations + and × on g can be calculated as binary operations. by using the set of hash keys k not only the entries of s and all the 1-mismatch subsequences are referred to, but also the other entries are. for example, when s is not a code word, subsequences of 2-mismatch belongs to the same equivalence class e. therefore, the hash key c refers to these subsequences. to analyze the properties of these subsequences, we define a reference formula: where s is a subsequence, k is a set of hash keys, and the coefficient a represents the number of subsequences that are referred to by k and whose distance from s is b. for case because s is the code word, all the 1-mismatch subsequences belong to e. therefore, the reference formula for case is: for case there are hash keys in k because the equivalence class of c has 2-mismatch subsequences, the reference formula of c is: each of the equivalence classes of the other hash keys has two 1-mismatch sequences, five 2-mismatch sequences and nine 3-mismatch sequences. the reference formula of k – {c} is: finally, the reference formula for the case is: the reference formula shows the proposed method searches many 2- and 3-mismatch sequences. we discuss this feature in section discussion. the above algorithm and analysis can be applied to the word length the numbers of hash keys are and for case and case respectively. using the rate of occurrences of case and case 1/ and 63/ respectively, the expected number of hash keys is. the reference formulas are shows in table to refer to all the entries of 2-mismatches, our method requires hash keys, which is % of the number of subsequences with or fewer mismatches. when the length of subsequences is figure shows the subsequence s and its surroundings when s is a code word. the number of subsequences of exact 2-mismatches |n2| is and the elements of |n2| are neighbors of n each n ∈ n has two neighbors of n and each n belongs to an equivalence class that contains other two elements of n in other words, equivalence classes are required to cover n in total, the number of required keys k is the reference formula is: in case s is not a code word and figure shows 2-mismatch sequences of s. the equivalence classes 2-mismatch subsequences belong to are classified into four types. type 1: 2-mismatch subssequences belong to this type are neighbors of c. type 2: for some t such that dh = and c ≠ c, 2-mismatch subsequences are neighbors of t belonging to c. type 3: for some t such that dh = and c ≠ c, they are neighbors of t not belonging to c. type 4: for some u such that dh = and c = c, they are neighbors of u not belonging to c. types and are included in k and the numbers of subsequences are and respectively. the equivalence classes of type are the right-most circles in figure similar to subsequences of 2-mismatches in figure three 2-mismatch subsequences belong to each equivalence class. the number of equivalence classes is eight and they includes 2-mismatch subsequences. the bottom-left circle in figure represents type the relation between of types and looks similar to that between types and in fact, type is a union of k – c for over each possible u. as the size of u is type has equivalence classes. in total, the number of hash keys to refer to 2-mismatch subsequences is. the reference formula is as follows: in the same manner, we can analyze the hash keys k for the subsequence of length of in this case, the reference formula when s = c becomes: and the formula when s ≠ c is: search n-gaps to align dna subsequence and a genome, there are three types of gaps. these are gaps in short dna sequence, gaps in genome sequence, and gaps in both. our method can reduce the number of hash keys to refer to gaps in short dna sequences. given a subsequence with gaps s, hash keys to refer to the genome positions are a set of code words of subsequences which with the gaps of s are substituted with nucleotides. the expected numbers of hash keys are and when the length of a subsequence with one gap is and respectively. let s be a subsequence with one-gap, such as “aa-aa”, and s be a set of subsequences for which a gap in s is substituted with a nucleotide, in this case the set comprising “aaaaa”, “aacaa”, “aagaa”, and “aataa”. to find the genome position that matches s, we need to refer to entries that correspond to s. when a subsequence t ∈ s is a code word, all the subsequences in s belong to the same equivalence class. therefore, by using c as a hash key, all the entries correspond to gapped subsequence s can be referred to from. in this case, the reference formula becomes + 12x, where the index number of x represents the minimum distance from the four subsequences in s. if no t ∈ s is a code word, the four subsequences belong to different equivalence classes. therefore, four hash keys are required and the reference formula is + 60x. the proportion for which one member of s is a code word is |s|/# of words in a equivalence class = 4/ = 1/ and so the expected number of hash keys is. in the same way, when the length is the expected number of hash keys is. the reference formulas are shown in table next, we consider a subsequence with two gaps. let s be a subsequence of length with two gaps such as “a-a-a” and s be the set of sequences for which the gaps in s are replaced with nucleotides. the number of information digits in -phc is and so one of words in s is a code word t. the code word t is the only code word in s because the maximum hamming distance among words in s is which equals the number of gaps, and the minimum hamming distance between code words is the equivalence class e includes seven subsequences of s; let u be the remaining subsequences ). because u ∈ u is not a code word and dh = the distance between t and the code word c is,t) = 3). this implies that c and t differ at a non-gapped position in t. therefore, for all u, v ∈ u, u ≠ v and d, v) = d + ≥ thus, all the subsequences in u belong to different equivalence classes and nine hash keys are required to refer to 2-gap subsequences. for example, if s=“a-a-a”, s includes a code word t =“aaaaa” and t can refer to sequences: “aaaaa”, “acaaa”, “agaaa”, “ataaa”, “aaaca”, “aaaga”, and “aaata”. the set of remaining subsequences are u = {“acaca”, “acaga”, “acata”, “agaca”, “agaga”, “agata”, “ataca”, “ataga”, “ataga” }. let u ∈ u = “acaca”. the code cord c is “acacc” and hamming distance from the rest of u are two or three. therefore, all subsequences in u belong to different equivalence classes. length of subsequence the code length of the phc is restricted to or in practice. this is inconvenient. therefore, we next explain ways to elongate the code length. there are four ways to elongate the code length. the first way is to simply add nucleotides before or/and after the code words. two other ways are serialization and parallelization of phcs. the former method serializes more than two phcs and serialized code words are used as the hash key. the latter one uses more than two hash tables for the parallelization and is a way to utilize the pigeonhole principle where pigeons are mismatches or gaps and holes are the regions without mismatches and gaps. the fourth way is a combination of the three. figure shows the concepts behind each. in the following, we show a serialized code and a parallelized code, both of length let s = s1s be a sequence of length and s and s be the subsequences of length the hash key used in the serialization to store s is cc. in this case, each equivalence class holds subsequences. to refer to the entry of a sequence s = s1s and the 1-mismatch sequences, the set of hash keys is: and the expected number of hash keys is. to prove this, we consider four cases: case s and s are both code words. case s is a code word, but s is not. case s is a code word, but s is not. case neither s nor s is a code word. in case use s1s as a hash key; this can refer to all the 1-mismatches. the reference formula in this case is the square of the reference formula of length = + 30x + 225x in case we need to consider two subcases based on the position of the 1-mismatch. when the position is in the first half of s, the hash key s1s can refer to all of them. when the position is in the second half, the second half of the hash keys becomes one of the seven words in k therefore, a set of hash keys is: because s ∈ k the hash keys in the second subcase include the hash keys in the first subcase. therefore, the number of hash keys |k1| is the reference formula is: in case similar to in case the set of hash keys is: and the reference formula is same as that of case in case the set of hash keys is the union of {s1t|t ∈ k1} and {ts2|t ∈ k1}, which correspond to 1-mismatch in the first half and 1-mismatch in the second half, respectively. because both of these include cc, the number of hash keys is. the reference formula is: the proportions of cases through of 1/ 15/ 15/ and 225/ respectively, and so the expected number of hash keys is. the parallelization requires two hash tables and each subsequence is stored in both hash tables. therefore, the total size of the hash tables is twice that of serialization. the hash keys are cs2: the first haf is phc, and s1c: the second half is phc. consequently, two types of equivalence classes are used in the parallelization and each equivalence class holds subsequences. the set of hash keys for 1-mismatch sequences is: where each set corresponds to one of the two hash tables. the expectation number of keys is. let us consider the four cases, which are the same as those for serialization. in case use s1s as the hash key for two hash tables and all the entries of 1-mismatch are referred to. in this case, the reference formula is + – = + 30x. as a subsequence s1s is stored in both hash tables, one is subtracted in the formula. though the number of hash keys appears to be one, it is used twice. thus the number of hash keys |k1| is two. in case the hash keys are: the total number hash keys is and the reference formula is: case is similar to case in this case the hash keys are: in case the hash keys when the first half includes the mismatch are {ts2|t ∈ k1} and that for the second half are {s1t|t ∈ k1}. the number of hash keys is and the reference formula is: the proportions of the cases are same as for serialization, and the expected number of hash keys is. discussion to search genome positions of n-mismatches and n-gaps with our method, table shows it also searches some positions of n+α-mismatch. for example, our method searches not only perfect match and 1-mismatch subsequences, but also 2-mismatches and 3-mismatches as byproducts % and % of all 2- and 3-mismatches, respectively. this proportion increases to %, 20% when l = these byproducts are, in fact, effective. one reason for the current low mapping ratios from dna sequencers of short reads to a genome is the small number of mismatches and gaps that the employed mapping method can find. therefore, increasing the numbers of mismatches and gaps will contribute to increasing the mapping ratio and subsequent biological analyses, even if the method is probabilistic. the increasing demand to map massive amounts of short dna sequences to genomes is inevitable. because the number of short sequences is enormous, it is difficult to ensure finding all genome positions of 1-mismatches in a practical computation time. therefore, faster methods are required and the proposed method is a step in that direction. we have shown that the proposed method can reduce the number of keys necessary to find the genome positions of n-mismatches. the main idea behind the method is to classify the subsequences into equivalence classes using phc. because equivalence classes contain multiple subsequences, our method can increase the density of the hash table over those using in the usual method. that is to say, our method can use longer subsequences. for example, the size of human genome is about 3g bases long. when this is stored it with subsequences of length in usual way, the density of the hash table is × 1012/ ≈ %. on the other hand, the hash table using our proposed method using -phc, the density is × 1012/ = × 1012/ ≈ %. that is to say, our method can use longer subsequences. the length of subsequence is sensitive to the efficiency of the genome-mapping programs, and the longer the better, for a given density of hash table. therefore, the proposed method has an advantage from this point of view. we consider the computation time for code words is far shorter than a hash reference when we describe the effectiveness of the proposed method. in practice, the calculation of the syndrome using the parity-check matrix of the hamming code is very short, even if on gf, and so it is easy to calculate the code word from a subsequence. also, the calculation is small enough to be executed within a cpu cache. on the other hand, the size of hash table is larger than the size of cpu caches. some exceeds the size of memory because the number of entries is almost equal to the length of the target genome. the hash reference is apparently slower than the calculation of the code word. therefore, the advantage of reducing the hash references exceeds the disadvantage of additional tasks to calculate code words. with these advantages, our method will help to implement faster genome mapping programs.  the paper shows perfect hamming code can reduce the number of hash references for hash-based genome mapping. the method encodes subsequences to perfect hamming codes on gf and use them as hash keys. it can reduce by about 70% the number of hash keys necessary for searching the genome positions of all 2-mismatches of 21-base-long dna subsequence. as the amount of data that dna sequencers generates continues to increase and more accurate genome mappings are required, our method will help to develop faster genome mapping software. competing interests the authors declare that they have no competing interests. authors' contributions yt provide the key idea and the mathematical analyses. ss and hm provide valuable help on the topics. all authors discusses the results and commented on the manuscript. supplementary material additional file 1 dna sequences and their code words. all the 5-mer dna sequences and their code words on 4-ary -perfect hamming codes. click here for file acknowledgements this work was partially supported by kakenhi and. this article has been published as part of bmc genomics volume supplement 2011: tenth international conference on bioinformatics – first iscb asia joint conference: computational biology. the full contents of the supplement are available online at http://www.biomedcentral.com/1471-2164/12?issue=s 
 november- december asia pacific bioinformatics network tenth international conference on bioinformatics – first iscb asia joint conference kuala lumpur, malaysia the method regards dna subsequences as words on galois extension field gf and each word is encoded to a code word of a perfect hamming code. each equivalence class includes subsequence whose corresponding words on gf are encoded to a corresponding code word. the code word is used as a hash key to store these subsequences in a hash table. as the computation time to calculate code words is far shorter than a hash reference, our method is effective to reduce the computation time to map short dna sequences to genome. the perfect hamming code defines equivalence classes of dna subsequences. the paper shows perfect hamming code can reduce the number of hash references for hash-based genome mapping. specifically, it reduces by about 70% the number of hash keys necessary for searching the genome positions of all 2-mismatches of 21-base-long dna subsequence. we propose a hash-based method for genome mapping that reduces the number of hash references for finding mismatches without increasing the size of the hash table. with the advent of next-generation sequencers, the growing demands to map short dna sequences to a genome have promoted the development of fast algorithms and tools. the amount of data that dna sequencers generate continues to increase and more accurate genome mappings are required. to find n-mismatches, they requires o times the computation time of exact matches. these algorithms are the best suited to finding the genome position of exactly matching short reads. the tools commonly used today are based on either a hash table or the suffix array/burrow–wheeler transform.
 with the advent of next-generation sequencers, the growing demands to map short dna sequences to a genome have promoted the development of fast algorithms and tools. the tools commonly used today are based on either a hash table or the suffix array/burrow–wheeler transform. these algorithms are the best suited to finding the genome position of exactly matching short reads. however, they have limited capacity to handle the mismatches. to find n-mismatches, they requires o times the computation time of exact matches. therefore, acceleration techniques are required.  we propose a hash-based method for genome mapping that reduces the number of hash references for finding mismatches without increasing the size of the hash table. the method regards dna subsequences as words on galois extension field gf and each word is encoded to a code word of a perfect hamming code. the perfect hamming code defines equivalence classes of dna subsequences. each equivalence class includes subsequence whose corresponding words on gf are encoded to a corresponding code word. the code word is used as a hash key to store these subsequences in a hash table. specifically, it reduces by about 70% the number of hash keys necessary for searching the genome positions of all 2-mismatches of 21-base-long dna subsequence.  the paper shows perfect hamming code can reduce the number of hash references for hash-based genome mapping. as the computation time to calculate code words is far shorter than a hash reference, our method is effective to reduce the computation time to map short dna sequences to genome. the amount of data that dna sequencers generate continues to increase and more accurate genome mappings are required. thus our method will be a key technology to develop faster genome mapping software. november- december asia pacific bioinformatics network tenth international conference on bioinformatics – first iscb asia joint conference kuala lumpur, malaysia 