BACKGROUND
mutations introduce variations and divergence into dna sequences within and among species.
differences among dna sequences are extensively used to identify species  <cit> .
for example, specific oligonucleotides have already been used in the polymerase chain reaction  method to identify  <dig> human pathogenic yeast species  <cit> .
a unique dna signature is a sequence that occurs in a dna database only once, and has some minimum mutation distance from all other sequences in the database.
unique signature discovery  <cit>  is the finding of unique signatures in a set of dna sequences.
they are accelerating various areas of research, including the map-based cloning of genes that control traits, comparative genome analysis, protein identification, and the development of various methods that depend on gene-specific oligonucleotides, such as the dna microarray technology.
the methods of signature discovery have been widely studied, and many related tools and applications have been developed  <cit> .
for example,  <cit>  integrates multiple bioinformatics algorithms to determine horizontally transferred, pathotype-specific signature genes as targets for specific, high-throughput molecular diagnostic applications and reverse vaccinology screens; insignia  <cit>  is a web application for rapidly identifying unique dna signatures, and hybseek  <cit>  is a web service for efficiently designing both pathogen-specific and compatible primer pairs for dna-based diagnostic multi-analyte assays.
the algorithm of zheng et al.
<cit>  and imus  <cit>  are two hamming-distance-based unique signature discovery algorithms.
these two algorithms deal with dna databases.
let l and d be two positive integers, where d ≤ l. an l-pattern is a string of l characters in the alphabet set {a, c, g, t}.
a pattern p is -mismatched to a pattern q if the length of p and q is l and the hamming distance, which is the number of mismatches, between p and q does not exceed d. an l-pattern p is referred to as a unique signature with mismatch tolerance d if and only if no other pattern q exists in the given dna database such that p and q are -mismatched.
zheng's algorithm and the imus algorithm are designed for efficiently discovering the unique signatures under the discovery conditions of signature length l and mismatch tolerance d.
zheng's algorithm, called the uo algorithm hereafter, is based on the observation that if two patterns, p and q, are -mismatched, then at least one of the partitions of λ p is -mismatched to the corresponding part in q, where λ = ⌊d/2⌋ +  <dig> and all partitions have equal length.
the uo algorithm is a two-phase algorithm.
in the first phase, the algorithm divides dna sequences into patterns of length l/λ.
an index system is built based on the l/λ-patterns as index keys, in which l-patterns that contain the same index key are gathered in a single index entry.
assume that kp is an index key, and kq is one of the keys that are -mismatched to kp.
in the second phase, the uo algorithm performs complete string comparisons on the l-patterns in the entries kq and kp to check whether they are -mismatched.
the unique signatures emerge after all of the duplicated patterns have been pruned.
the imus algorithm improves upon the uo algorithm.
the imus algorithm is based on the observation that if two patterns p and q are -mismatched, then at least one of the two halves of p is -mismatched to the corresponding part of q. in the processing-kernel level, the uo and imus algorithms are similar.
the main difference between them is the number of partitions in an l-pattern.
the imus algorithm divides an l-pattern into two partitions, whereas the uo algorithm divides a pattern into ⌊d/2⌋ +  <dig> partitions.
since the mismatch tolerance d is small  in most discoveries of short signatures , the imus algorithm reduces the number of partitions in an l-pattern to decrease the number of required string comparisons, and thus increases the discovery efficiency.
a consequence is that more memory is required to store the index that is used in the imus algorithm.
an additional frequency filter, which represents an enhanced usage of the frequency distance, defined in  <cit> , is used in the imus algorithm as a pre-filter to prevent unnecessary comparisons between dissimilar patterns.
however, most signature discovery algorithms have the problem that we do not know how to select proper factor values, such as the proper  values in the uo or imus algorithm, because the proper discovery result is defined on a case-by-case basis.
in most cases, factor values are selected based on domain knowledge or experience or even by guessing.
the factor settings are then used in the discovery algorithm to discover signatures.
if the result is unacceptable, then the factor values are changed to get other results.
the process is repeated until satisfactory results are found.
this situation often arises when an unfamiliar dna database is being used.
a method that can efficiently find all of the signatures that satisfy feasible discovery conditions, instead of repeated trial and error, enabling users to select the proper signatures, is needed.
in other words, when the discovery condition is given in terms of signature length l and mismatch tolerance d, a discovery algorithm can be use to discover not only the signatures with exact  but also all signatures that meet stricter discovery conditions - with a length smaller than l or a mismatch tolerance larger than d. then, the signatures that meet our requirements can be selected directly from the results.
the signatures of length ≤ l and mismatch tolerance ≥ d are called the implicit signatures under the discovery condition .
providing researchers with all implicit signatures without manually changing the factor values would be helpful.
one challenge is how to discover efficiently all implicit signatures from dna databases under a certain discovery condition.
an intuitive solution is to use the uo or imus algorithm iteratively to perform a complete discovery under all feasible discovery conditions.
however, this solution is not sufficiently efficient.
the uo and imus algorithms are specifically designed for discovering signatures that meet a certain discovery condition, but they cannot discover all of the implicit signatures.
accordingly, an efficient algorithm for discovering all implicit signatures under a certain discovery condition is needed.
the idea of the 'incremental' has been used in many research areas, such as data mining and knowledge discovery  <cit> , communications  <cit>  and computer graphics and visualization  <cit> .
the definitions of the term 'incremental' vary slightly among fields.
here, 'incremental' is used to refer to the fact that a new result is obtained by processing the previously discovered signatures, rather than by performing a complete discovery on the whole database.
additionally, since an increasing number of computers have multi-core processors, parallel computing is applied to accelerate the signature discovery processes.
this work proposes an algorithm that is called the consecutive multiple discovery  algorithm, which is designed specifically for discovering all implicit signatures under a certain discovery condition from dna databases.
the cmd algorithm is an iterative algorithm.
it includes an algorithm called parallel and incremental signature discovery  algorithm as a kernel routine.
the pisd algorithm enhances the hamming-distance-based unique signature discovery algorithms, the uo and imus algorithms, by using the incremental and parallel computing techniques.
the pisd algorithm is based on observations of hamming-distance-based signatures, and discovers new results by reusing previously discovered signatures but with looser discovery conditions.
for example, the algorithm can find signatures of length l =  <dig> and mismatch tolerance d =  <dig> by processing the signatures of l =  <dig> and d =  <dig>  the scope of the search is far smaller than the size of the input database.
the pisd algorithm runs faster than the typical uo and imus algorithms because it reuses the discovered signatures as candidates, rather than all of the patterns in the database.
based on the results from the experiments on human chromosome  <dig> est databases, the proposed cmd algorithm discovers all implicit signatures and performs  <dig>  times faster than the typical algorithm when eight processing cores are used.
RESULTS
algorithm
the proposed consecutive multiple discovery  algorithm efficiently discovers all of the implicit signatures of length ≤ l and mismatch tolerance ≥ d under the discovery condition .
the cmd algorithm uses the parallel and incremental signature discovery  algorithm as a kernel routine.
given a discovery condition , the pisd algorithm is designed for efficiently discovering signatures of length l' and tolerance d', and then the cmd algorithm uses the pisd to find all of the implicit signatures of length l' ≤ l and mismatch tolerance d' ≥ d. the pisd algorithm is based on observations of the hamming-distance-based signatures, and uses parallel computing to increase discovery efficiency.
the pisd algorithm applies a scheduling heuristic, which is called the parallel entry list  heuristic, to generate a reordered entry list when parallel computing is used.
this entry list improves the performance of the proposed pisd algorithm.
the parallel and incremental signature discovery  algorithm
let Ωl, d denote the set of the unique signatures discovered by the uo or imus algorithm under the discovery condition .
we have the observations as follows:
observation  <dig>  ∀p ∈ Ωl- <dig>  d, p must be a substring of a pattern q in Ωl, d.
proof.
assume p ∈ Ωl- <dig>  d and p' is a pattern of length l -  <dig>  since p is a signature of condition , hd >d, where hd is the hamming distance between p and p'.
let x be a character in {a, c, g, t}.
assume q = x + p and q' is a pattern of length l, where + means string concatenation.
hd = hd ≥ hd > d, where  is the i-th character of q' and  denotes the substring starting from the i-th to the j-th characters in q'.
hence, p is a substring of q and q ∈ Ωl, d in this case.
the proof of the case with q = p + x can be done in the same way, yielding the result that p is a substring of q and q ∈ Ωl, d.
therefore, the observation holds.
observation  <dig>  ∀ p ∈ Ωl, d+ <dig>  p must be in Ωl, d.
proof.
assume p ∈ Ωl, d+ <dig> and p' is a pattern of length l. since p ∈ Ωl, d+ <dig>  hd >d +  <dig> >d, where hd is the hamming distance between p and p'.
thus, p ∈ Ωl, d. the observation holds.
observation  <dig>  ∀p ∈ Ωl-a, d+b, p must be a substring of a pattern q in Ωl,d, where a and b are positive integers, and a <l.
the observations can be used to improve the hamming-distance-based signature discovery algorithms, including the uo and imus algorithms.
based on these observations, the unique signatures of factors  must be discoverable from the unique signatures that satisfy the discovery condition , where l' ≤ l and d' ≥ d. accordingly, the discovery is incremental, reducing the scope of the search in the discovery process.
hereafter, this heuristic is called 'incremental discovery'.
for example, table  <dig> presents a dna database of three sequences.
table  <dig> lists the five patterns in the database.
table  <dig> presents Ω <dig> , Ω <dig> , Ω <dig>  and Ω <dig> .
each pattern in Ω <dig>  is in Ω <dig> , and all of the patterns in Ω <dig>  and Ω <dig>  are implicit in Ω <dig> .
restated, to discover Ω <dig> , Ω <dig>  or Ω <dig> , the patterns in Ω <dig>  can be used as candidates, instead of all of the patterns in the database.
since the number of patterns in Ω <dig> ,  <dig>  is less than the number of patterns in the database,  <dig>  the discovery process is accelerated.
let Ωl, d denote the set of the unique signatures of length l and mismatch tolerance d. the result shows that all of the patterns in Ω <dig> , Ω <dig>  and Ω <dig>  are implicit in Ω <dig> .
additional file  <dig> presents the pisd algorithm.
let l' be the desired signature length and d' be the mismatch tolerance.
divide all of the dna sequences in the input database into α-patterns, where the value of α is related to the selected hamming-distance-based signature discovery algorithm.
for example, α = l'/ <dig> for the imus algorithm, and α = l'/ for the uo algorithm.
a l'-pattern comprises l'/α consecutive α-patterns.
an index of 4α entries is built with the α-patterns as index keys.
a multi-level index can be adopted if the index is too large to be fit in the main memory.
the l'-patterns that contain a certain α-pattern are collected in an entry.
each entry maintains a list of the locations of the pattern in the database, which is called a pattern list.
the patterns in the input database are called data patterns, and the patterns that are discovered by a hamming-distance-based signature discovery algorithm are referred to as candidate patterns.
based on the observations of hamming-distance-based discovery and incremental discovery, the new result obtained under stricter discovery conditions can be discovered from the candidate patterns obtained under looser conditions.
to accelerate access, the candidate patterns are arranged in the pattern list in an entry prior to the non-candidate patterns.
a pointer indicates the end of the candidate patterns in the pattern list.
a processing order list of all of the entries in the index is constructed.
if a multiple-processor system is used, then the processing order list is generated by the pel heuristic ; otherwise, the order list includes the entries in an arbitrary order.
observation  <dig>   if two patterns, p and q, are -mismatched, then at least one of the  partitions of p is -mismatched to the corresponding part in q, where α = l'/ and all partitions have equal length.
observation  <dig>   if two patterns p and q are -mismatched, then at least one of the two halves of p is -mismatched to the corresponding part of q, where α = l'/ <dig>
two index entries are called similar entries if the number of mismatches between the keys of the entries is less than or equal to a certain value β. this value is also related to the employed discovery algorithm, for example, β is  <dig> in the uo algorithm, and β = ⌊d'/2⌋ in the imus algorithm.
assume kp and kq are index keys, and p and q are the l'-patterns listed in the entries of keys kp and kq, respectively.
based on observations  <dig> and  <dig>  if q is -mismatched to p, then kq must be -mismatched to kp, such that the entries of keys kp and kq are similar.
since all the patterns that are -mismatched to a pattern p must be in the entries that are similar to the entry whose key is kp, p is compared to all of the patterns in the similar entries, to determine whether p is unique.
the pattern p is a unique signature if no pattern is -mismatched to it.
since the new result can be discovered from the candidate patterns, the pisd processes only the candidate patterns.
an available processor is assigned to handle the next untreated entry  in the processing order list.
assume that p is one of the candidate patterns in the entry.
p is compared to all of the patterns in the similar entries, which are those whose keys are -mismatched to kp.
each of the comparisons is a complete string comparison of l' characters.
the candidate l'-patterns that are -mismatched to any of the l'-patterns in the similar entries are discarded, and the remaining candidate patterns are new unique signatures.
the scheduling heuristic for parallelism
one of the ways to accelerate signature discovery is to apply parallel computing.
assume that a computer of n processors is employed in signature discovery, and that processor i takes ti time units to complete its tasks.
the overall processing time tn required by the computer to complete the discovery is , which means that the processor that takes longest dominates the overall processing time.
the optimal processing time when n processors are used is tn = t1/n, which equals 1/n of the processing time of a single-processor computer.
the simplest way to apply parallel computing to the proposed pisd algorithm is to assign randomly an available processor to process the patterns in the index in an arbitrary order.
the treatment of an entry is referred to as a task.
for example, a computer with four processors is used to handle n tasks.
processor  <dig> can be assigned to task  <dig>  ..., and processor  <dig> can be assigned to task  <dig>  assume that processor  <dig> is the first to complete its task; the processor is immediately assigned to the next task, task  <dig>  the next available processor is similarly assigned to the next task until all of the n tasks are completed.
if four tasks are processed simultaneously, then ideally, the overall processing time is reduced to one quarter of that which would be required using a single-processor computer.
however, two potential problems must be considered when parallel computing is applied to the proposed pisd algorithm.
first, if one of the last few tasks requires much processing time, then the overall processing time may be longer than the optimal processing time.
for example, figure  <dig> shows a list of six tasks.
all of the tasks can be completed in  <dig> time units by a single-processor computer.
the optimal processing time is therefore 22/ <dig> =  <dig> units for a two-processor computer.
however, in this case, processor  <dig> is assigned to {a, d, f}, and processor  <dig> is assigned to {b, c, e}.
the processing times are  <dig> and  <dig> units respectively, and the overall processing time is  <dig> units, which exceeds the optimal processing time.
this situation can be avoided by arranging long tasks before the others in the processing order list.
here, the long tasks are moved forward in the processing order list, yielding the result in figure  <dig>  in the new list, processor  <dig> performs tasks {f, d} and processor  <dig> performs tasks {a, c, e, b}.
the overall processing time is  <dig> units, which equals the optimal processing time.
the second potential problem is that the time required to process a task may exceed the optimal processing time, t1/n.
for example, figure  <dig> shows a list of six tasks.
all of the tasks can be completed in  <dig> units by a single-processor computer.
when a two-processor computer is used to handle the tasks, processors  <dig> and  <dig> are assigned to tasks {a, c, e} and {b, d, f}, and taking  <dig> and  <dig> units, respectively.
the overall processing time is  <dig> units.
long tasks are moved forward, yielding the new processing order list that is shown in figure  <dig>  in this situation, processor  <dig> is assigned to task f only, and processor  <dig> is assigned to the other tasks.
the overall processing time is then  <dig> units, which still exceeds the optimal processing time, because task f takes  <dig> units, which exceeds the sum of the times required to complete all of the other tasks.
hence if less time were to be spent on task f, then the overall processing time would be reduced.
generally, when an entry has more patterns than the other entries, a task that handles this entry takes more time to complete.
therefore, some of the longest entries are divided into n equal partitions, which are then treated as typical entries, where n is the number of available processors.
for example, task f in figure  <dig> can be divided into two tasks with identical processing times, yielding the new task list in figure  <dig>  after the division, processor  <dig> is assigned to tasks {f <dig>  b, d, a}, and processor  <dig> is assigned to tasks {f <dig>  c, e}.
the overall processing time is  <dig> units, which equals the optimal processing time.
based on the above discussion, the order of tasks in the processing order list influences the overall processing time for parallel discovery.
since the proposed discovery algorithm pisd focuses on processing candidate patterns, the processing time of a task is proportional to the number of candidate patterns in the entry.
the index entries can be sorted in descending order of the number of candidate patterns therein, and the sorted list can be used as the processing order list.
entries that contain more candidate patterns are expected to be at the top of the list.
however, the sorting process takes o time for n entries, which is significant.
a simple and efficient scheduling heuristic, called the parallel entry list , is provided.
it yields a processing order list for tasks in which the tasks that involve more candidate patterns are before those that involve fewer.
additional file  <dig> displays the pel heuristic.
the pel heuristic is similar to a partial quicksort.
unlike quicksort, the pel heuristic is iterative, and only operates on the left part of a list in each iteration.
firstly, the pel heuristic generates a processing order list l that consists of all of the index entries in arbitrary order, and w is defined as the number of index entries in l. the average number of candidate patterns  in each entry is computed, where g equals /w.
let li represent the i-th entry in l, and || be the number of candidate patterns in li.
then, the pel heuristic searches for the maximal value r such that || >g and the minimal value k such that || ≤ g, and then exchanges lk and lr.
the searches and exchanges continue until r <k.
the process scans the entries from l <dig> to lw in l and w is updated to the current value of r. then, the entries in l are divided into two parts: if i ≤ w, then || >g; otherwise, || ≤ g. assume w' is the most recent value of the variable w. since || >g, ∀ i ≤ w, w <w'/ <dig>  then, the pel heuristic focuses on the first part of l, and moves the long entries forward until , where n is the number of available processors and n is the number of index entries in l. now, the first w entries in l are the top w entries, which contain the most candidate patterns.
the first w entries are removed from l, and the candidate patterns in each entry are divided into n partitions of equal number of patterns.
the nw partitions are then put into l, and treated as typical entries in successive processes.
the total number of scans performed on is , where m is the number of iterations of the main outer loop , which moves the long entries forward.
the time complexity of the pel heuristic is o = o.
as an example of the above, consider an entry list l, shown in table  <dig>  the average number of candidate patterns in each entry  is  <dig>  the leftmost entry in l that contains fewer than g candidate patterns, and the rightmost entry that contains more than g candidate patterns are sought.
the respective results are entries a and j. these two entries are exchanged in l. entries b and g as well as d and e are similarly exchanged.
table  <dig> shows the new processing order list.
now, w is four, and the number of candidate patterns in each of the first w =  <dig> entries exceeds g =  <dig>  while that in the other entries is less than  <dig>  then, only the region of the first four entries is considered in the next step.
the average number of the candidate patterns in each entry within this region is computed, yielding g =  <dig>  in this region, the leftmost and rightmost entries that contain fewer than and more than  <dig> candidate patterns are j and e, respectively.
j and e are exchanged in the list, yielding table  <dig>  assume a two-processor computer is used.
entry e is divided into two partitions e <dig> and e <dig>  and e <dig> and e <dig> are added to the list.
the new list is as shown in table  <dig>  processor  <dig> will handle entries e <dig>  g, d, f, b, i and a, and processor  <dig> will handle entries e <dig>  c, j, h and k. the total number of candidate patterns to be treated by each processor is  <dig>
let |*| denote the number of candidate patterns in an entry.
part  presents the original entry list.
entries a and j, b and g as well as d and e are exchanged.
part  presents the new entry list.
entries j and e are exchanged in the next iteration, yielding part .
assume a two-processor computer is used.
entry e is divided into two partitions e <dig> and e <dig>  and e <dig> and e <dig> are added to the list.
the new list is as shown in part .
the consecutive multiple discovery  algorithm
additional file  <dig> displays the consecutive multiple discovery  algorithm.
let l and d be two integers.
the cmd algorithm is an iterative algorithm, which uses the pisd algorithm as a kernel routine, to discover all implicit signatures under the discovery condition of length l and mismatch tolerance d. firstly, the uo or imus algorithm is used to discover the unique signatures that satisfy the discovery condition .
the signatures discovered by uo or imus are applied as candidates in successive discoveries.
the feasible discovery conditions are all combinations of the possible l' and d', which means {}.
in each discovery, the pisd algorithm is used to discover new signatures from the candidates under a feasible discovery condition.
the discovery process continues until all of the implicit signatures are discovered.
testing
this section evaluates the performance of the proposed algorithms.
since the incremental discovery and parallel computing mentioned in the previous sections can be applied to the uo and imus algorithms, briefly, the cmd  with the uo and imus kernels are denoted as cmduo and cmdimus , respectively.
the algorithms are analyzed based on a uniformly distributed database.
the first part of this section presents these analyses.
to evaluate the performance of the uo, imus, cmduo and cmdimus algorithms, they are applied to human chromosome  <dig> and  <dig> est databases for signature discovery.
the second part of this section presents the experimental results.
mathematical analyses
the cmd algorithm is an iterative algorithm.
it includes the pisd algorithm as a kernel routine.
accordingly, the time complexity of the pisd algorithm dominates that of the cmd algorithm.
first, the time complexity of the pisduo algorithm is analyzed under a certain discovery condition, and then, the results are integrated, yielding the time complexity of the cmduo algorithm.
the analyses of the pisdimus and cmdimus algorithms can be done in a similar way.
let l' be the signature length and d' be the mismatch tolerance.
σl' denotes the index system built under the condition of signature length l' in the pisduo algorithm.
σl' consists of 4α pattern entries, where α = l'/ is the length of the entry keys.
let σl', i be the i-th entry in σl'·|σl', i| denotes the number of all patterns in σl', i and  denotes the number of candidate patterns in σl', i. hd denotes the hamming distance between σl', i and σl', j, which is defined as the hamming distance between the entry keys of σl', i and σl', j. because only the candidate patterns have to be considered, |σl', i| string comparisons are performed on the patterns in σl', i. additionally, ∑j|σl', j| string comparisons are required to check possible mutants, where σl', j ∈ σl' such that hd =  <dig>  all characters in an l'-pattern excluding the entry key region are compared in each of the string comparisons, yielding l' - α character comparisons.
the total amount of character comparisons used in the pisduo algorithm, denoted as , is:
where σl', j ∈ σl' such that hd =  <dig>
let l be the desired signature length and d be the mismatch tolerance of pattern uniqueness.
the cmduo algorithm uses the pisduo algorithm to find all of the implicit signatures of length l' ≤ l and mismatch tolerance d' ≥ d. the time complexity of the cmduo algorithm, denoted as , is:
where σl', j ∈ σl' such that hd =  <dig>
assume the input dna database d and the set of the discovered signatures Ωl' ≤ l, d' ≥ d are uniformly distributed.
let  ∈ {Ωx, y}l' ≤ x ≥ l and d ≤ y ≥ d'}, where  ≠ , be the set of signatures discovered in the strictest iteration prior to the iteration of .
assume the sizes of d and  are denoted as |d| and ||.
the index system built in this uniformly distributed case is denoted as .
each entry in  should contain || ≈ |d|/4α patterns, and  of them are candidate patterns.
in this case, the amount of character comparisons used in the pisduo algorithm, denoted as , is:
where σl', j ∈ σl' such that hd =  <dig>  and κ = 3α is the number of all possible  <dig> base permutations of a string of length α. note that  because of the uniform assumption.
in the uniformly distributed case, the number of character comparisons used in the cmduo algorithm, denoted as , is:
where κ = 3α.
the main difference between the pisduo and the typical uo algorithms is that the two algorithms use different candidate sets.
the pisduo algorithm uses the previously discovered signatures as candidates, but the uo algorithm uses all of the patterns in the database as candidates.
the amount of character comparisons used in the uo algorithm for discovering signatures from the uniformly distributed database d can be obtained by replacing  with d. the formula is:
where κ = 3α.
the uo algorithm is executed repeatedly to discover all implicit signatures.
the time complexity of using the uo algorithm, denoted as , is:
where κ = 3α.
the gain delivered by the cmduo algorithm is:
where κ = 3α.
it means that the cmduo algorithm performs g ≥ |d|/|Ωl, d| times faster than the typical uo algorithm, when discovering implicit signatures from a uniformly distributed database.
performance evaluation
the platform that was adopted in this experiment was a dell poweredge r <dig> server with two intel xeon e <dig>  <dig>  ghz quad-core cpus,  <dig> gb ram and  <dig> gb disk space.
the operating system was red hat enterprise linux  <dig>  the algorithms were implemented in java language, and the programs were compiled by jdk  <dig> .
the dna data that were used in the experiments were from the human chromosome  <dig> and  <dig> est databases.
before the experiments, the remarks in the databases were removed; all of the universal characters, such as 'don't care', were replaced with 'a', and dna sequences that were shorter than  <dig> bases were discarded.
the experimental data are denoted as d <dig>  and d <dig> , and their corresponding sizes were approximately  <dig>  m and  <dig>  m bases.
the pooled oligo probes, that are used to screen an est library, such as the bac library, generally have lengths from  <dig> to  <dig> bases  <cit> .
our experimental results on unique signature discoveries, with the criteria of exact matches, also shows that most of the human est sequences can be distinctly labeled by signatures of length greater than  <dig> bases.
accordingly, the experiments in this section focused on discovering signatures of length between  <dig> and  <dig> with mismatch tolerances of two and four.
for reasons of performance and memory consumption, a two-level index was used in the implementation of the imus and cmdimus algorithms.
the first level of the index comprised  <dig> direct-accessible entries, and a binary search was used to locate a specified entry in the second level.
the index systems that were used in the implementation of the uo and cmduo algorithms were one-level, and all of the entries in their index systems were directly accessible.
since the purpose of our experiments was to evaluate the improvements provided by incremental discovery and parallel computing, additional filters, such as the frequency filter that was used in the imus algorithm, was excluded from the kernels of the algorithms.
since ⌊d/2⌋ +  <dig> =  <dig> when d =  <dig>  the kernels of the uo and imus algorithms are very similar under this condition.
only the performance of the imus and cmdimus algorithms was examined when mismatch tolerance was two.
table  <dig> presents the discovery conditions that were used in our experiments.
in the experiments on the uo and imus algorithms, the uo and imus algorithms were executed repeatedly to discover all of the signatures under all feasible discovery conditions.
the experiments were performed on a one-processor computer.
before the performance of the cmduo and cmdimus algorithms was evaluated, the imus algorithm was used to discover signatures under the discovery condition of length l =  <dig> and mismatch tolerance d =  <dig>  the discovery on d <dig> took approximately  <dig>  minutes and  <dig> % of the patterns from d <dig> were discovered as signatures.
the discovery on d <dig> took about  <dig>  minutes and  <dig> % of the patterns from d <dig> were discovered as signatures.
in each successive experiment, the cmduo and cmdimus algorithms used the discovered signatures of l =  <dig> and d =  <dig> as candidates to produce new results.
• indicates that the discovery condition was used in the experiments by the specified algorithm.
the percentage time saved is used to evaluate the improvements in the processing time of an algorithm.
the time saving is defined as  algorithm)/ algorithm))*100%.
a larger 'saving' means a greater improvement by the cmduo or cmdimus algorithm.
the term 'overall' refers to the total processing time required for the uo, imus, cmduo or cmdimus algorithm to discover all of the signatures that satisfy the discovery conditions.
first, improvements in the time of discovery associated with incremental discovery are examined.
for a single processing core, the performance of the cmduo and cmdimus algorithms was evaluated by using the algorithms to discover signatures from d <dig> and d <dig>  tables  <dig> and  <dig> present the processing time that for the uo and imus algorithms, and the time savings delivered by the cmduo and cmdimus algorithms.
the tables also present the processing time required to discover signatures under every discovery condition.
in the experiments, the proposed cmduo algorithm took  <dig> % less processing time than the uo algorithm to discover all of the implicit signatures from d <dig>  and about 74% less processing time to discover those from d <dig>  with respect to the performance of the cmdimus algorithm, it took about 67% and 52% less processing time than the imus algorithm to discover all of the signatures from d <dig> and d <dig>  greater overheads in accessing indices caused the percentage processing time saved by the cmdimus algorithm to be less than that saved by the cmduo algorithm.
the table presents the processing time that for the uo algorithm, and the time savings delivered by the cmduo algorithm.
the time format used in the table is hh:mm:ss.
the table presents the processing time that for the imus algorithm, and the time savings delivered by the cmdimus algorithm.
the time format used in the table is hh:mm:ss.
to elucidate the benefits of parallel computing for signature discovery, various number of processing cores were used and the pisduo and pisdimus algorithms were used to discover the signatures of  from d <dig>  table  <dig> shows the experimental results: the acceleration is the processing time normalized to the processing time when one processor is used.
when the pisduo algorithm is used, the acceleration of the discovery processes is almost proportional to the number of processing cores used.
the acceleration values of the pisdimus algorithm increase with the number of processing cores such that the discovery process using eight processing cores is approximately  <dig>  times faster than that using a single core.
with various number of processing cores, the pisduo and pisdimus algorithms were used to discover the signatures of  from d <dig>  the table shows the experimental results.
the acceleration is the processing time normalized to the processing time when one processor is used.
the time format used in the table is hh:mm:ss.
finally, the improvements in the discovery performance delivered by a combination of incremental discovery and parallel computing are examined.
in this case, the cmduo and cmdimus algorithms discovered signatures from the databases using eight processing cores.
tables  <dig> and  <dig> present the time savings made by the cmduo and cmdimus algorithms.
tables  <dig> and  <dig> show the number of discovered signatures under each discovery condition.
in the experiments, the proposed cmduo algorithm took 97% less processing time than the uo algorithm to discover all of the implicit signatures from d <dig>  and about  <dig> % less processing time to complete discovery on d <dig>  the cmdimus algorithm took about  <dig> % and  <dig> % less processing time than the imus algorithm, to discover all of the signatures from the experimental data d <dig> and d <dig>  respectively.
the cmduo algorithm discovered signatures from the databases using eight processing cores.
the table presents the time savings made by the cmduo algorithm.
the time format used in the table is hh:mm:ss.
the cmdimus algorithm discovered signatures from the databases using eight processing cores.
the table presents the time savings made by the cmdimus algorithm.
the time format used in the table is hh:mm:ss.
the cmduo algorithm discovered signatures from the databases using eight processing cores.
the table presents the number of discovered signatures under each discovery condition.
the cmdimus algorithm discovered signatures from the databases using eight processing cores.
the table presents the number of discovered signatures under each discovery condition.
the experimental results reveal that the cmduo and cmdimus algorithms with one processing core require up to 76% and 67% less processing time to find all implicit signatures than the typical uo and imus algorithms, respectively.
moreover, up to 97% and 93% of the processing time is saved when the cmduo and cmdimus algorithms are executed using eight processing cores.
restated, the proposed cmduo and cmdimus algorithms perform  <dig>  and  <dig>  times faster than the typical uo and imus algorithms when one processing core is used, and  <dig>  and  <dig>  times faster when eight processing cores are used.
CONCLUSIONS
this work proposes two unique signature discovery algorithms - the consecutive multiple discovery  algorithm and the parallel and incremental signature discovery  algorithm.
the cmd algorithm is designed to discover all implicit signatures from dna databases, providing all implicit signatures to users, especially when they are using an unfamiliar dna database.
the pisd algorithm is a parallel and incremental enhancement of existing signature discovery algorithms.
it is based on incremental discovery, and efficiently discovers signatures under a certain discovery condition.
this incremental strategy can be adapted to all hamming-distance-based unique signature discovery algorithms.
the pisd algorithm has a significantly shorter processing time for signature discovery than typical discovery algorithms.
the pisd algorithm is the kernel of the cmd algorithm.
consequently, the cmd algorithm provides an efficient means of implicit signature discovery.
authors' contributions
hpl carried out the unique signature studies, participated in the design of the study, programmed the algorithms, evaluated the experimental results and drafted the manuscript.
tfs participated in its design and coordination, performed the mathematical analysis and drafted the manuscript.
cyt convinced of the study and helped to gather data.
all authors read and approved the final manuscript.
supplementary material
additional file 1
parallel and incremental signature discovery  algorithm.
assume l' is the desired signature length and d' is the mismatch tolerance.
α and β are two integers that are related to the selected hamming-distance-based signature discovery algorithm.
α = l'/ <dig> and β = ⌊d'/2⌋ for the imus algorithm, and α = l'/ and β =  <dig> for the uo algorithm.
the algorithm is designed for efficiently discovering signatures under the discovery condition .
click here for file
additional file 2
parallel entry list  heuristic.
the heuristic yields a processing order list for index entries in which the entries that involve more candidate patterns are before those that involve fewer.
the reordered entry list improves the performance of the proposed pisd algorithm.
click here for file
additional file 3
consecutive multiple discovery  algorithm.
let l be the desired signature length and d be the mismatch tolerance of pattern uniqueness.
the algorithm discovers all implicit signatures under the discovery condition .
click here for file
acknowledgements
the authors would like to thank the national science council of the republic of china, taiwan, for financially supporting this research under grants 98-2218-e-126-001-my <dig>

 mutations introduce variations and divergence into dna sequences within and among species. differences among dna sequences are extensively used to identify species. for example, specific oligonucleotides have already been used in the polymerase chain reaction method to identify human pathogenic yeast species. a unique dna signature is a sequence that occurs in a dna database only once, and has some minimum mutation distance from all other sequences in the database. unique signature discovery is the finding of unique signatures in a set of dna sequences. they are accelerating various areas of research, including the map-based cloning of genes that control traits, comparative genome analysis, protein identification, and the development of various methods that depend on gene-specific oligonucleotides, such as the dna microarray technology. the methods of signature discovery have been widely studied, and many related tools and applications have been developed. for example, integrates multiple bioinformatics algorithms to determine horizontally transferred, pathotype-specific signature genes as targets for specific, high-throughput molecular diagnostic applications and reverse vaccinology screens; insignia is a web application for rapidly identifying unique dna signatures, and hybseek is a web service for efficiently designing both pathogen-specific and compatible primer pairs for dna-based diagnostic multi-analyte assays. the algorithm of zheng et al. and imus are two hamming-distance-based unique signature discovery algorithms. these two algorithms deal with dna databases. let l and d be two positive integers, where d ≤ l. an l-pattern is a string of l characters in the alphabet set {a, c, g, t}. a pattern p is -mismatched to a pattern q if the length of p and q is l and the hamming distance, which is the number of mismatches, between p and q does not exceed d. an l-pattern p is referred to as a unique signature with mismatch tolerance d if and only if no other pattern q exists in the given dna database such that p and q are -mismatched. zheng's algorithm and the imus algorithm are designed for efficiently discovering the unique signatures under the discovery conditions of signature length l and mismatch tolerance d. zheng's algorithm, called the uo algorithm hereafter, is based on the observation that if two patterns, p and q, are -mismatched, then at least one of the partitions of λ p is -mismatched to the corresponding part in q, where λ = ⌊d/2⌋ + and all partitions have equal length. the uo algorithm is a two-phase algorithm. in the first phase, the algorithm divides dna sequences into patterns of length l/λ. an index system is built based on the l/λ-patterns as index keys, in which l-patterns that contain the same index key are gathered in a single index entry. assume that kp is an index key, and kq is one of the keys that are -mismatched to kp. in the second phase, the uo algorithm performs complete string comparisons on the l-patterns in the entries kq and kp to check whether they are -mismatched. the unique signatures emerge after all of the duplicated patterns have been pruned. the imus algorithm improves upon the uo algorithm. the imus algorithm is based on the observation that if two patterns p and q are -mismatched, then at least one of the two halves of p is -mismatched to the corresponding part of q. in the processing-kernel level, the uo and imus algorithms are similar. the main difference between them is the number of partitions in an l-pattern. the imus algorithm divides an l-pattern into two partitions, whereas the uo algorithm divides a pattern into ⌊d/2⌋ + partitions. since the mismatch tolerance d is small in most discoveries of short signatures, the imus algorithm reduces the number of partitions in an l-pattern to decrease the number of required string comparisons, and thus increases the discovery efficiency. a consequence is that more memory is required to store the index that is used in the imus algorithm. an additional frequency filter, which represents an enhanced usage of the frequency distance, defined in, is used in the imus algorithm as a pre-filter to prevent unnecessary comparisons between dissimilar patterns. however, most signature discovery algorithms have the problem that we do not know how to select proper factor values, such as the proper values in the uo or imus algorithm, because the proper discovery result is defined on a case-by-case basis. in most cases, factor values are selected based on domain knowledge or experience or even by guessing. the factor settings are then used in the discovery algorithm to discover signatures. if the result is unacceptable, then the factor values are changed to get other results. the process is repeated until satisfactory results are found. this situation often arises when an unfamiliar dna database is being used. a method that can efficiently find all of the signatures that satisfy feasible discovery conditions, instead of repeated trial and error, enabling users to select the proper signatures, is needed. in other words, when the discovery condition is given in terms of signature length l and mismatch tolerance d, a discovery algorithm can be use to discover not only the signatures with exact but also all signatures that meet stricter discovery conditions - with a length smaller than l or a mismatch tolerance larger than d. then, the signatures that meet our requirements can be selected directly from the results. the signatures of length ≤ l and mismatch tolerance ≥ d are called the implicit signatures under the discovery condition. providing researchers with all implicit signatures without manually changing the factor values would be helpful. one challenge is how to discover efficiently all implicit signatures from dna databases under a certain discovery condition. an intuitive solution is to use the uo or imus algorithm iteratively to perform a complete discovery under all feasible discovery conditions. however, this solution is not sufficiently efficient. the uo and imus algorithms are specifically designed for discovering signatures that meet a certain discovery condition, but they cannot discover all of the implicit signatures. accordingly, an efficient algorithm for discovering all implicit signatures under a certain discovery condition is needed. the idea of the'incremental' has been used in many research areas, such as data mining and knowledge discovery, communications and computer graphics and visualization. the definitions of the term'incremental' vary slightly among fields. here,'incremental' is used to refer to the fact that a new result is obtained by processing the previously discovered signatures, rather than by performing a complete discovery on the whole database. additionally, since an increasing number of computers have multi-core processors, parallel computing is applied to accelerate the signature discovery processes. this work proposes an algorithm that is called the consecutive multiple discovery algorithm, which is designed specifically for discovering all implicit signatures under a certain discovery condition from dna databases. the cmd algorithm is an iterative algorithm. it includes an algorithm called parallel and incremental signature discovery algorithm as a kernel routine. the pisd algorithm enhances the hamming-distance-based unique signature discovery algorithms, the uo and imus algorithms, by using the incremental and parallel computing techniques. the pisd algorithm is based on observations of hamming-distance-based signatures, and discovers new results by reusing previously discovered signatures but with looser discovery conditions. for example, the algorithm can find signatures of length l = and mismatch tolerance d = by processing the signatures of l = and d = the scope of the search is far smaller than the size of the input database. the pisd algorithm runs faster than the typical uo and imus algorithms because it reuses the discovered signatures as candidates, rather than all of the patterns in the database. based on the results from the experiments on human chromosome est databases, the proposed cmd algorithm discovers all implicit signatures and performs times faster than the typical algorithm when eight processing cores are used.  algorithm the proposed consecutive multiple discovery algorithm efficiently discovers all of the implicit signatures of length ≤ l and mismatch tolerance ≥ d under the discovery condition. the cmd algorithm uses the parallel and incremental signature discovery algorithm as a kernel routine. given a discovery condition, the pisd algorithm is designed for efficiently discovering signatures of length l' and tolerance d', and then the cmd algorithm uses the pisd to find all of the implicit signatures of length l' ≤ l and mismatch tolerance d' ≥ d. the pisd algorithm is based on observations of the hamming-distance-based signatures, and uses parallel computing to increase discovery efficiency. the pisd algorithm applies a scheduling heuristic, which is called the parallel entry list heuristic, to generate a reordered entry list when parallel computing is used. this entry list improves the performance of the proposed pisd algorithm. the parallel and incremental signature discovery algorithm let Ωl, d denote the set of the unique signatures discovered by the uo or imus algorithm under the discovery condition. we have the observations as follows: observation ∀p ∈ Ωl- d, p must be a substring of a pattern q in Ωl, d. proof. assume p ∈ Ωl- d and p' is a pattern of length l - since p is a signature of condition, hd >d, where hd is the hamming distance between p and p'. let x be a character in {a, c, g, t}. assume q = x + p and q' is a pattern of length l, where + means string concatenation. hd = hd ≥ hd > d, where is the i-th character of q' and denotes the substring starting from the i-th to the j-th characters in q'. hence, p is a substring of q and q ∈ Ωl, d in this case. the proof of the case with q = p + x can be done in the same way, yielding the result that p is a substring of q and q ∈ Ωl, d. therefore, the observation holds. observation ∀ p ∈ Ωl, d+ p must be in Ωl, d. proof. assume p ∈ Ωl, d+ and p' is a pattern of length l. since p ∈ Ωl, d+ hd >d + >d, where hd is the hamming distance between p and p'. thus, p ∈ Ωl, d. the observation holds. observation ∀p ∈ Ωl-a, d+b, p must be a substring of a pattern q in Ωl,d, where a and b are positive integers, and a <l. the observations can be used to improve the hamming-distance-based signature discovery algorithms, including the uo and imus algorithms. based on these observations, the unique signatures of factors must be discoverable from the unique signatures that satisfy the discovery condition, where l' ≤ l and d' ≥ d. accordingly, the discovery is incremental, reducing the scope of the search in the discovery process. hereafter, this heuristic is called'incremental discovery'. for example, table presents a dna database of three sequences. table lists the five patterns in the database. table presents Ω, Ω, Ω and Ω. each pattern in Ω is in Ω, and all of the patterns in Ω and Ω are implicit in Ω. restated, to discover Ω, Ω or Ω, the patterns in Ω can be used as candidates, instead of all of the patterns in the database. since the number of patterns in Ω, is less than the number of patterns in the database, the discovery process is accelerated. let Ωl, d denote the set of the unique signatures of length l and mismatch tolerance d. the result shows that all of the patterns in Ω, Ω and Ω are implicit in Ω. additional file presents the pisd algorithm. let l' be the desired signature length and d' be the mismatch tolerance. divide all of the dna sequences in the input database into α-patterns, where the value of α is related to the selected hamming-distance-based signature discovery algorithm. for example, α = l'/ for the imus algorithm, and α = l'/ for the uo algorithm. a l'-pattern comprises l'/α consecutive α-patterns. an index of 4α entries is built with the α-patterns as index keys. a multi-level index can be adopted if the index is too large to be fit in the main memory. the l'-patterns that contain a certain α-pattern are collected in an entry. each entry maintains a list of the locations of the pattern in the database, which is called a pattern list. the patterns in the input database are called data patterns, and the patterns that are discovered by a hamming-distance-based signature discovery algorithm are referred to as candidate patterns. based on the observations of hamming-distance-based discovery and incremental discovery, the new result obtained under stricter discovery conditions can be discovered from the candidate patterns obtained under looser conditions. to accelerate access, the candidate patterns are arranged in the pattern list in an entry prior to the non-candidate patterns. a pointer indicates the end of the candidate patterns in the pattern list. a processing order list of all of the entries in the index is constructed. if a multiple-processor system is used, then the processing order list is generated by the pel heuristic; otherwise, the order list includes the entries in an arbitrary order. observation if two patterns, p and q, are -mismatched, then at least one of the partitions of p is -mismatched to the corresponding part in q, where α = l'/ and all partitions have equal length. observation if two patterns p and q are -mismatched, then at least one of the two halves of p is -mismatched to the corresponding part of q, where α = l'/ two index entries are called similar entries if the number of mismatches between the keys of the entries is less than or equal to a certain value β. this value is also related to the employed discovery algorithm, for example, β is in the uo algorithm, and β = ⌊d'/2⌋ in the imus algorithm. assume kp and kq are index keys, and p and q are the l'-patterns listed in the entries of keys kp and kq, respectively. based on observations and if q is -mismatched to p, then kq must be -mismatched to kp, such that the entries of keys kp and kq are similar. since all the patterns that are -mismatched to a pattern p must be in the entries that are similar to the entry whose key is kp, p is compared to all of the patterns in the similar entries, to determine whether p is unique. the pattern p is a unique signature if no pattern is -mismatched to it. since the new result can be discovered from the candidate patterns, the pisd processes only the candidate patterns. an available processor is assigned to handle the next untreated entry in the processing order list. assume that p is one of the candidate patterns in the entry. p is compared to all of the patterns in the similar entries, which are those whose keys are -mismatched to kp. each of the comparisons is a complete string comparison of l' characters. the candidate l'-patterns that are -mismatched to any of the l'-patterns in the similar entries are discarded, and the remaining candidate patterns are new unique signatures. the scheduling heuristic for parallelism one of the ways to accelerate signature discovery is to apply parallel computing. assume that a computer of n processors is employed in signature discovery, and that processor i takes ti time units to complete its tasks. the overall processing time tn required by the computer to complete the discovery is, which means that the processor that takes longest dominates the overall processing time. the optimal processing time when n processors are used is tn = t1/n, which equals 1/n of the processing time of a single-processor computer. the simplest way to apply parallel computing to the proposed pisd algorithm is to assign randomly an available processor to process the patterns in the index in an arbitrary order. the treatment of an entry is referred to as a task. for example, a computer with four processors is used to handle n tasks. processor can be assigned to task..., and processor can be assigned to task assume that processor is the first to complete its task; the processor is immediately assigned to the next task, task the next available processor is similarly assigned to the next task until all of the n tasks are completed. if four tasks are processed simultaneously, then ideally, the overall processing time is reduced to one quarter of that which would be required using a single-processor computer. however, two potential problems must be considered when parallel computing is applied to the proposed pisd algorithm. first, if one of the last few tasks requires much processing time, then the overall processing time may be longer than the optimal processing time. for example, figure shows a list of six tasks. all of the tasks can be completed in time units by a single-processor computer. the optimal processing time is therefore 22/ = units for a two-processor computer. however, in this case, processor is assigned to {a, d, f}, and processor is assigned to {b, c, e}. the processing times are and units respectively, and the overall processing time is units, which exceeds the optimal processing time. this situation can be avoided by arranging long tasks before the others in the processing order list. here, the long tasks are moved forward in the processing order list, yielding the result in figure in the new list, processor performs tasks {f, d} and processor performs tasks {a, c, e, b}. the overall processing time is units, which equals the optimal processing time. the second potential problem is that the time required to process a task may exceed the optimal processing time, t1/n. for example, figure shows a list of six tasks. all of the tasks can be completed in units by a single-processor computer. when a two-processor computer is used to handle the tasks, processors and are assigned to tasks {a, c, e} and {b, d, f}, and taking and units, respectively. the overall processing time is units. long tasks are moved forward, yielding the new processing order list that is shown in figure in this situation, processor is assigned to task f only, and processor is assigned to the other tasks. the overall processing time is then units, which still exceeds the optimal processing time, because task f takes units, which exceeds the sum of the times required to complete all of the other tasks. hence if less time were to be spent on task f, then the overall processing time would be reduced. generally, when an entry has more patterns than the other entries, a task that handles this entry takes more time to complete. therefore, some of the longest entries are divided into n equal partitions, which are then treated as typical entries, where n is the number of available processors. for example, task f in figure can be divided into two tasks with identical processing times, yielding the new task list in figure after the division, processor is assigned to tasks {f b, d, a}, and processor is assigned to tasks {f c, e}. the overall processing time is units, which equals the optimal processing time. based on the above discussion, the order of tasks in the processing order list influences the overall processing time for parallel discovery. since the proposed discovery algorithm pisd focuses on processing candidate patterns, the processing time of a task is proportional to the number of candidate patterns in the entry. the index entries can be sorted in descending order of the number of candidate patterns therein, and the sorted list can be used as the processing order list. entries that contain more candidate patterns are expected to be at the top of the list. however, the sorting process takes o time for n entries, which is significant. a simple and efficient scheduling heuristic, called the parallel entry list, is provided. it yields a processing order list for tasks in which the tasks that involve more candidate patterns are before those that involve fewer. additional file displays the pel heuristic. the pel heuristic is similar to a partial quicksort. unlike quicksort, the pel heuristic is iterative, and only operates on the left part of a list in each iteration. firstly, the pel heuristic generates a processing order list l that consists of all of the index entries in arbitrary order, and w is defined as the number of index entries in l. the average number of candidate patterns in each entry is computed, where g equals /w. let li represent the i-th entry in l, and || be the number of candidate patterns in li. then, the pel heuristic searches for the maximal value r such that || >g and the minimal value k such that || ≤ g, and then exchanges lk and lr. the searches and exchanges continue until r <k. the process scans the entries from l to lw in l and w is updated to the current value of r. then, the entries in l are divided into two parts: if i ≤ w, then || >g; otherwise, || ≤ g. assume w' is the most recent value of the variable w. since || >g, ∀ i ≤ w, w <w'/ then, the pel heuristic focuses on the first part of l, and moves the long entries forward until, where n is the number of available processors and n is the number of index entries in l. now, the first w entries in l are the top w entries, which contain the most candidate patterns. the first w entries are removed from l, and the candidate patterns in each entry are divided into n partitions of equal number of patterns. the nw partitions are then put into l, and treated as typical entries in successive processes. the total number of scans performed on is, where m is the number of iterations of the main outer loop, which moves the long entries forward. the time complexity of the pel heuristic is o = o. as an example of the above, consider an entry list l, shown in table the average number of candidate patterns in each entry is the leftmost entry in l that contains fewer than g candidate patterns, and the rightmost entry that contains more than g candidate patterns are sought. the respective results are entries a and j. these two entries are exchanged in l. entries b and g as well as d and e are similarly exchanged. table shows the new processing order list. now, w is four, and the number of candidate patterns in each of the first w = entries exceeds g = while that in the other entries is less than then, only the region of the first four entries is considered in the next step. the average number of the candidate patterns in each entry within this region is computed, yielding g = in this region, the leftmost and rightmost entries that contain fewer than and more than candidate patterns are j and e, respectively. j and e are exchanged in the list, yielding table assume a two-processor computer is used. entry e is divided into two partitions e and e and e and e are added to the list. the new list is as shown in table processor will handle entries e g, d, f, b, i and a, and processor will handle entries e c, j, h and k. the total number of candidate patterns to be treated by each processor is let |*| denote the number of candidate patterns in an entry. part presents the original entry list. entries a and j, b and g as well as d and e are exchanged. part presents the new entry list. entries j and e are exchanged in the next iteration, yielding part. assume a two-processor computer is used. entry e is divided into two partitions e and e and e and e are added to the list. the new list is as shown in part. the consecutive multiple discovery algorithm additional file displays the consecutive multiple discovery algorithm. let l and d be two integers. the cmd algorithm is an iterative algorithm, which uses the pisd algorithm as a kernel routine, to discover all implicit signatures under the discovery condition of length l and mismatch tolerance d. firstly, the uo or imus algorithm is used to discover the unique signatures that satisfy the discovery condition. the signatures discovered by uo or imus are applied as candidates in successive discoveries. the feasible discovery conditions are all combinations of the possible l' and d', which means {}. in each discovery, the pisd algorithm is used to discover new signatures from the candidates under a feasible discovery condition. the discovery process continues until all of the implicit signatures are discovered. testing this section evaluates the performance of the proposed algorithms. since the incremental discovery and parallel computing mentioned in the previous sections can be applied to the uo and imus algorithms, briefly, the cmd with the uo and imus kernels are denoted as cmduo and cmdimus, respectively. the algorithms are analyzed based on a uniformly distributed database. the first part of this section presents these analyses. to evaluate the performance of the uo, imus, cmduo and cmdimus algorithms, they are applied to human chromosome and est databases for signature discovery. the second part of this section presents the experimental results. mathematical analyses the cmd algorithm is an iterative algorithm. it includes the pisd algorithm as a kernel routine. accordingly, the time complexity of the pisd algorithm dominates that of the cmd algorithm. first, the time complexity of the pisduo algorithm is analyzed under a certain discovery condition, and then, the results are integrated, yielding the time complexity of the cmduo algorithm. the analyses of the pisdimus and cmdimus algorithms can be done in a similar way. let l' be the signature length and d' be the mismatch tolerance. σl' denotes the index system built under the condition of signature length l' in the pisduo algorithm. σl' consists of 4α pattern entries, where α = l'/ is the length of the entry keys. let σl', i be the i-th entry in σl'·|σl', i| denotes the number of all patterns in σl', i and denotes the number of candidate patterns in σl', i. hd denotes the hamming distance between σl', i and σl', j, which is defined as the hamming distance between the entry keys of σl', i and σl', j. because only the candidate patterns have to be considered, |σl', i| string comparisons are performed on the patterns in σl', i. additionally, ∑j|σl', j| string comparisons are required to check possible mutants, where σl', j ∈ σl' such that hd = all characters in an l'-pattern excluding the entry key region are compared in each of the string comparisons, yielding l' - α character comparisons. the total amount of character comparisons used in the pisduo algorithm, denoted as, is: where σl', j ∈ σl' such that hd = let l be the desired signature length and d be the mismatch tolerance of pattern uniqueness. the cmduo algorithm uses the pisduo algorithm to find all of the implicit signatures of length l' ≤ l and mismatch tolerance d' ≥ d. the time complexity of the cmduo algorithm, denoted as, is: where σl', j ∈ σl' such that hd = assume the input dna database d and the set of the discovered signatures Ωl' ≤ l, d' ≥ d are uniformly distributed. let ∈ {Ωx, y}l' ≤ x ≥ l and d ≤ y ≥ d'}, where ≠, be the set of signatures discovered in the strictest iteration prior to the iteration of. assume the sizes of d and are denoted as |d| and ||. the index system built in this uniformly distributed case is denoted as. each entry in should contain || ≈ |d|/4α patterns, and of them are candidate patterns. in this case, the amount of character comparisons used in the pisduo algorithm, denoted as, is: where σl', j ∈ σl' such that hd = and κ = 3α is the number of all possible base permutations of a string of length α. note that because of the uniform assumption. in the uniformly distributed case, the number of character comparisons used in the cmduo algorithm, denoted as, is: where κ = 3α. the main difference between the pisduo and the typical uo algorithms is that the two algorithms use different candidate sets. the pisduo algorithm uses the previously discovered signatures as candidates, but the uo algorithm uses all of the patterns in the database as candidates. the amount of character comparisons used in the uo algorithm for discovering signatures from the uniformly distributed database d can be obtained by replacing with d. the formula is: where κ = 3α. the uo algorithm is executed repeatedly to discover all implicit signatures. the time complexity of using the uo algorithm, denoted as, is: where κ = 3α. the gain delivered by the cmduo algorithm is: where κ = 3α. it means that the cmduo algorithm performs g ≥ |d|/|Ωl, d| times faster than the typical uo algorithm, when discovering implicit signatures from a uniformly distributed database. performance evaluation the platform that was adopted in this experiment was a dell poweredge r server with two intel xeon e ghz quad-core cpus, gb ram and gb disk space. the operating system was red hat enterprise linux the algorithms were implemented in java language, and the programs were compiled by jdk. the dna data that were used in the experiments were from the human chromosome and est databases. before the experiments, the remarks in the databases were removed; all of the universal characters, such as'don't care', were replaced with'a', and dna sequences that were shorter than bases were discarded. the experimental data are denoted as d and d, and their corresponding sizes were approximately m and m bases. the pooled oligo probes, that are used to screen an est library, such as the bac library, generally have lengths from to bases. our experimental results on unique signature discoveries, with the criteria of exact matches, also shows that most of the human est sequences can be distinctly labeled by signatures of length greater than bases. accordingly, the experiments in this section focused on discovering signatures of length between and with mismatch tolerances of two and four. for reasons of performance and memory consumption, a two-level index was used in the implementation of the imus and cmdimus algorithms. the first level of the index comprised direct-accessible entries, and a binary search was used to locate a specified entry in the second level. the index systems that were used in the implementation of the uo and cmduo algorithms were one-level, and all of the entries in their index systems were directly accessible. since the purpose of our experiments was to evaluate the improvements provided by incremental discovery and parallel computing, additional filters, such as the frequency filter that was used in the imus algorithm, was excluded from the kernels of the algorithms. since ⌊d/2⌋ + = when d = the kernels of the uo and imus algorithms are very similar under this condition. only the performance of the imus and cmdimus algorithms was examined when mismatch tolerance was two. table presents the discovery conditions that were used in our experiments. in the experiments on the uo and imus algorithms, the uo and imus algorithms were executed repeatedly to discover all of the signatures under all feasible discovery conditions. the experiments were performed on a one-processor computer. before the performance of the cmduo and cmdimus algorithms was evaluated, the imus algorithm was used to discover signatures under the discovery condition of length l = and mismatch tolerance d = the discovery on d took approximately minutes and % of the patterns from d were discovered as signatures. the discovery on d took about minutes and % of the patterns from d were discovered as signatures. in each successive experiment, the cmduo and cmdimus algorithms used the discovered signatures of l = and d = as candidates to produce new results. • indicates that the discovery condition was used in the experiments by the specified algorithm. the percentage time saved is used to evaluate the improvements in the processing time of an algorithm. the time saving is defined as algorithm)/ algorithm))*100%. a larger'saving' means a greater improvement by the cmduo or cmdimus algorithm. the term'overall' refers to the total processing time required for the uo, imus, cmduo or cmdimus algorithm to discover all of the signatures that satisfy the discovery conditions. first, improvements in the time of discovery associated with incremental discovery are examined. for a single processing core, the performance of the cmduo and cmdimus algorithms was evaluated by using the algorithms to discover signatures from d and d tables and present the processing time that for the uo and imus algorithms, and the time savings delivered by the cmduo and cmdimus algorithms. the tables also present the processing time required to discover signatures under every discovery condition. in the experiments, the proposed cmduo algorithm took % less processing time than the uo algorithm to discover all of the implicit signatures from d and about 74% less processing time to discover those from d with respect to the performance of the cmdimus algorithm, it took about 67% and 52% less processing time than the imus algorithm to discover all of the signatures from d and d greater overheads in accessing indices caused the percentage processing time saved by the cmdimus algorithm to be less than that saved by the cmduo algorithm. the table presents the processing time that for the uo algorithm, and the time savings delivered by the cmduo algorithm. the time format used in the table is hh:mm:ss. the table presents the processing time that for the imus algorithm, and the time savings delivered by the cmdimus algorithm. the time format used in the table is hh:mm:ss. to elucidate the benefits of parallel computing for signature discovery, various number of processing cores were used and the pisduo and pisdimus algorithms were used to discover the signatures of from d table shows the experimental results: the acceleration is the processing time normalized to the processing time when one processor is used. when the pisduo algorithm is used, the acceleration of the discovery processes is almost proportional to the number of processing cores used. the acceleration values of the pisdimus algorithm increase with the number of processing cores such that the discovery process using eight processing cores is approximately times faster than that using a single core. with various number of processing cores, the pisduo and pisdimus algorithms were used to discover the signatures of from d the table shows the experimental results. the acceleration is the processing time normalized to the processing time when one processor is used. the time format used in the table is hh:mm:ss. finally, the improvements in the discovery performance delivered by a combination of incremental discovery and parallel computing are examined. in this case, the cmduo and cmdimus algorithms discovered signatures from the databases using eight processing cores. tables and present the time savings made by the cmduo and cmdimus algorithms. tables and show the number of discovered signatures under each discovery condition. in the experiments, the proposed cmduo algorithm took 97% less processing time than the uo algorithm to discover all of the implicit signatures from d and about % less processing time to complete discovery on d the cmdimus algorithm took about % and % less processing time than the imus algorithm, to discover all of the signatures from the experimental data d and d respectively. the cmduo algorithm discovered signatures from the databases using eight processing cores. the table presents the time savings made by the cmduo algorithm. the time format used in the table is hh:mm:ss. the cmdimus algorithm discovered signatures from the databases using eight processing cores. the table presents the time savings made by the cmdimus algorithm. the time format used in the table is hh:mm:ss. the cmduo algorithm discovered signatures from the databases using eight processing cores. the table presents the number of discovered signatures under each discovery condition. the cmdimus algorithm discovered signatures from the databases using eight processing cores. the table presents the number of discovered signatures under each discovery condition. the experimental results reveal that the cmduo and cmdimus algorithms with one processing core require up to 76% and 67% less processing time to find all implicit signatures than the typical uo and imus algorithms, respectively. moreover, up to 97% and 93% of the processing time is saved when the cmduo and cmdimus algorithms are executed using eight processing cores. restated, the proposed cmduo and cmdimus algorithms perform and times faster than the typical uo and imus algorithms when one processing core is used, and and times faster when eight processing cores are used.  this work proposes two unique signature discovery algorithms - the consecutive multiple discovery algorithm and the parallel and incremental signature discovery algorithm. the cmd algorithm is designed to discover all implicit signatures from dna databases, providing all implicit signatures to users, especially when they are using an unfamiliar dna database. the pisd algorithm is a parallel and incremental enhancement of existing signature discovery algorithms. it is based on incremental discovery, and efficiently discovers signatures under a certain discovery condition. this incremental strategy can be adapted to all hamming-distance-based unique signature discovery algorithms. the pisd algorithm has a significantly shorter processing time for signature discovery than typical discovery algorithms. the pisd algorithm is the kernel of the cmd algorithm. consequently, the cmd algorithm provides an efficient means of implicit signature discovery. authors' contributions hpl carried out the unique signature studies, participated in the design of the study, programmed the algorithms, evaluated the experimental results and drafted the manuscript. tfs participated in its design and coordination, performed the mathematical analysis and drafted the manuscript. cyt convinced of the study and helped to gather data. all authors read and approved the final manuscript. supplementary material additional file 1 parallel and incremental signature discovery algorithm. assume l' is the desired signature length and d' is the mismatch tolerance. α and β are two integers that are related to the selected hamming-distance-based signature discovery algorithm. α = l'/ and β = ⌊d'/2⌋ for the imus algorithm, and α = l'/ and β = for the uo algorithm. the algorithm is designed for efficiently discovering signatures under the discovery condition. click here for file additional file 2 parallel entry list heuristic. the heuristic yields a processing order list for index entries in which the entries that involve more candidate patterns are before those that involve fewer. the reordered entry list improves the performance of the proposed pisd algorithm. click here for file additional file 3 consecutive multiple discovery algorithm. let l be the desired signature length and d be the mismatch tolerance of pattern uniqueness. the algorithm discovers all implicit signatures under the discovery condition. click here for file acknowledgements the authors would like to thank the national science council of the republic of china, taiwan, for financially supporting this research under grants 98-2218-e-126-001-my 
such discovery algorithms require to set some input factors, such as signature length l and mismatch tolerance d, which affect the discovery results. implicit signatures under the discovery condition are defined as the signatures of length ≤ l with mismatch tolerance ≥ d. a discovery algorithm that could discover all implicit signatures, such that those that meet the requirements concerning the results, would be more helpful than one that depends on trial and error. the pisd algorithm is designed for efficiently discovering signatures under a certain discovery condition. it uses the pisd algorithm as a kernel routine to discover implicit signatures efficiently under every feasible discovery condition. the algorithm finds new results by using previously discovered results as candidates, rather than by using the whole database. biologists usually use a discovery algorithm to find unique signatures from dna databases, and then apply the signatures to microarray experiments. however, suggestions about how to select proper factor values are rare, especially when an unfamiliar dna database is used. the cmd algorithm is designed to discover implicit signatures efficiently. the presented cmd algorithm has up to 97% less execution time than typical sequential discovery algorithms in the discovery of implicit signatures in experiments, when eight processing cores are used. however, existing discovery algorithms do not address the need to discover all implicit signatures. this work proposes two discovery algorithms - the consecutive multiple discovery algorithm and the parallel and incremental signature discovery algorithm. if the discovered result is unsatisfactory, biologists change the input factors of the algorithm to obtain a new result. the pisd algorithm further increases discovery efficiency by applying parallel computing. the proposed algorithms discover implicit signatures efficiently.
 dna signatures are distinct short nucleotide sequences that provide valuable information that is used for various purposes, such as the design of polymerase chain reaction primers and microarray experiments. biologists usually use a discovery algorithm to find unique signatures from dna databases, and then apply the signatures to microarray experiments. such discovery algorithms require to set some input factors, such as signature length l and mismatch tolerance d, which affect the discovery results. however, suggestions about how to select proper factor values are rare, especially when an unfamiliar dna database is used. in most cases, biologists typically select factor values based on experience, or even by guessing. if the discovered result is unsatisfactory, biologists change the input factors of the algorithm to obtain a new result. this process is repeated until a proper result is obtained. implicit signatures under the discovery condition are defined as the signatures of length ≤ l with mismatch tolerance ≥ d. a discovery algorithm that could discover all implicit signatures, such that those that meet the requirements concerning the results, would be more helpful than one that depends on trial and error. however, existing discovery algorithms do not address the need to discover all implicit signatures.  this work proposes two discovery algorithms - the consecutive multiple discovery algorithm and the parallel and incremental signature discovery algorithm. the pisd algorithm is designed for efficiently discovering signatures under a certain discovery condition. the algorithm finds new results by using previously discovered results as candidates, rather than by using the whole database. the pisd algorithm further increases discovery efficiency by applying parallel computing. the cmd algorithm is designed to discover implicit signatures efficiently. it uses the pisd algorithm as a kernel routine to discover implicit signatures efficiently under every feasible discovery condition.  the proposed algorithms discover implicit signatures efficiently. the presented cmd algorithm has up to 97% less execution time than typical sequential discovery algorithms in the discovery of implicit signatures in experiments, when eight processing cores are used. 