text:
|Publication number
|Publication type
|Application number
|Publication date
|Aug 16, 2005
|Filing date
|May 6, 2002
|Priority date
|May 4, 2001
|Fee status
|Also published as
|Publication number
|Michael A. Gibson, Richard J. Messenger, Marc A. Rieffel, Zheng Zhang
|Original Assignee
|Paracel, Inc.
|Export Citation
|BiBTeX, EndNote, RefMan
|Patent Citations (5), Non-Patent Citations (11), Referenced by (59), Classifications (15), Legal Events (5)
|External Links: USPTO, USPTO Assignment, Espacenet
The present application claims the benefit of priority under 35 U.S.C. � 119(e) to U.S. Provisional Patent Application Ser. No. 60/288,465, entitled "Method and Apparatus for High-Speed Approximate Sub-String Searches," filed May 4, 2001, the entirety of which is incorporated by reference herein.
The present invention relates to string searching, and more specifically to computer implemented string searching of databases.
When a novel stretch of nucleic acid, e.g., DNA, or protein is first sequenced, its sequence is typically compared against a database of known DNA and protein information to provide a preliminary indication of the new DNA or protein's function. A researcher can then design experiments to assay the results of the database search.
As a result of the enormous improvement of DNA sequencing technology, the rate of growth of the DNA database has grown exponentially over the last decade from 1.5 million nucleotides per year in 1989 to over 1.6 billion nucleotides per year in 1999. Since 1999, entire genomes have been sequenced, including those of drosophila, mouse, and human. As the amount of known genetic sequence information increases exponentially, it becomes increasingly important to develop high speed methods to search the expanding sequence databases.
For example, GenBank, a public repository of genomic information, currently has nearly 16 GB of data, having grown from a mere 680 K in 1982 (Benson et al., Nucleic Acids Research, 28(1):15-18 (2000) (See also www.ncbi.nlm.nih.gov/Genbank/genbankstats.html.)). At that rate, the amount of data is doubling every 16.5 months. In 2001 alone, 3.5 million sequences totaling 3 GB of new sequence were entered into GenBank. Both public and private sequencing facilities consist of warehouse-sized factories generating data around the clock, limited only by the availability of reagents and the speed of the sequencing machines.
As more sequence data becomes available, one of the most basic problems is sequence alignment—how does a newly discovered nucleotide or amino acid sequence relate to previously known and studied data? Note that whenever the amount of sequence data doubles, the number of possible comparisons quadruples. Therefore, despite similarly impressive exponential doubling of computer speed on roughly the same time course, sequence comparison algorithms are falling farther and farther behind in their ability to find homologies for any significant part of the available data.
Much of the current research in homology searching focuses on algorithms that are more sensitive and selective—algorithms that use sophisticated techniques such as Hidden Markov Models to reduce the rate of false positives and false negatives, in other words to correctly identify weak homologies (e.g., genes in two very distantly related organisms), as described in, for example Eddy, "Profile Hidden Markov Models," Bioinformatics, 14(9):755-763 (1998), the entirety of which is incorporated by reference herein. Such algorithms push the envelope of mining the maximum amount of information from the data available, and are of enormous research interest. This invention takes a different track. For many applications, existing algorithms are good enough. In particular, the BLAST (Basic Local Alignment Search Tool) family of algorithms, developed by NCBI is sufficiently sensitive and selective for most searches. See, for example, Altschul, et al., "Gapped BLAST and PSI-BLAST: new generation of protein database search programs," Nucleic Acids Research, 25(17):389-3402 (1997), the entirety of which is incorporated by reference herein.
Basic Local Alignment Search Tool
Currently, the most common methods of high speed database are variants of the Basic Local Alignment Search Tool ("BLAST") described by Altschul, et al., J. Mol. Biol., 215(3):403-10 (1990), the entirety of which is incorporated by reference herein. BLAST and its variants provide a fast, local alignment of sequences. BLAST programs have been written to compare protein or DNA queries with protein or DNA databases in any combination, with DNA sequences often undergoing conceptual translation before any comparison is performed.
BLAST is a heuristic that attempts to optimize a similarity measure. Specifically, BLAST identifies all local regions of similarity (called High-scoring Segment Pairs or "HSPs") which can statistically be distinguished from random alignments. BLAST permits a tradeoff between speed and sensitivity, with the setting of a "threshold" parameter, T. A higher value of T yields greater speed, but also an increased probability of missing weak similarities. The BLAST program requires time proportional to the product of the lengths of the query sequence and the database searched.
The central idea of the BLAST algorithm is that a statistically significant alignment is likely to contain a high-scoring pair of aligned words. BLAST first scans the database for words (e.g., 3 for proteins and 12 for DNA) that score at least T when aligned with some word within the query sequence. Any aligned word pair satisfying this condition is called a "hit." The second step of the algorithm checks whether each hit lies within an alignment with a score sufficient to be reported. This is done by extending a hit in both directions, until the running alignment's score has dropped more than X below the maximum score yet attained.
In its most fundamental implementation, the BLAST algorithm performs three steps: (1) compile a list of high scoring words of length w from the query sequence; (2) for each sequence in the database, scan for word hits—i.e. words from the query sequence matching words in the database sequence—with scores greater than a threshold T; (3) for each word hit, extend it in both directions to form a High Scoring Pair ("HSP") of score greater than or equal to S. The to following paragraphs describe these steps in greater detail.
In a typical BLAST implementation, the list of high scoring words is compiled into a lookup table with i rows and j columns, where i is the number of all possible words of length w, and j is the number of elements in the query sequence minus w. Because the value i represents every possible word of length w, each row in the lookup table corresponds to one word of length w. The row number corresponds to the lexical order of its corresponding word, and can be considered the "row number" for that word. For DNA sequences i=4w; for protein sequences, i=20w. The value j represents the number of starting positions of words of length w in the query sequence. The lookup table is initialized with all zeroes, and then populated as follows: For every word of length w in the query, look up its corresponding row. Call this row x. Call the position of the word in the query sequence y. Set the (x,y) element of the lookup table to y. Once the lookup table is populated, it is then trimmed. Rows with all zeroes, representing words not present in the query, are removed. The remaining words are then screened for significance by examining them to see if their self-similarity score meets a minimum threshold T. Similarity scores are typically calculated using a substitution matrix such as PAM120 and BLOSUM62, as described in Dayhoff et al., Atlas of Protein Sequence and Structure, Vol. 5, Suppl. 3, Ed. M. O. Dayhoff (1978); Henikoff and Henikoff, Proc. Natl. Acad. Sci. USA, 89: 10915-10519 (1992); and Henikoff and Henikoff, Proteins, 17: 49-61 (1993). These publications are incorporated by reference herein in their entireties. Rows representing words with self-scores less than T are eliminated. Finally, all columns with zeroes are eliminated. The resulting lookup table is indexed by the lexical word number of significant words, and returns the position of significant words in the query sequence.
BLAST is a heuristic algorithm, and values of w and T are chosen for an optimal mix of sensitivity, specificity, and speed. As w increases for a given value of T, specificity is increased but sensitivity is decreased. Similarly, as T decreases for a given value of w, sensitivity is increased, but specificity is decreased and run time is increased. Exemplary settings of w and T are w=4, T=17 for proteins and w=12, T=60 for DNA.
Once the lookup table is constructed, it is used for comparing the query sequence against the database. Specifically, the database is searched for all words of length w that are present in the query sequence whose self-scores are higher than the threshold T. Every word thus found is called a "hit." The output of the database search comprises a list of hits. Because the database is searched repeatedly, it is first preprocessed into a lookup table similar to that generated for the query sequence. Thus, the search process can be performed quickly by comparing the two lookup tables.
The final step is to extend each hit to form a High-scoring Segment Pair ("HSP"). Typically, the hit is extended in both directions until the similarity score between the corresponding stretches of query sequence and database sequence fall below a predetermined threshold S.
The output of a typical BLAST implementation includes descriptions of hits found in the database. For each hit, the output includes information about the sequence from which the hit came, the hit's score in bits, the probability that a given HSP or HSPs would have been found by chance, and the E-value, which is a measure of the number of matches expected to have been found by chance in a database of this size for the given score.
Previous Improvements to BLAST
Implementations of the BLAST algorithm have undergone improvements since the algorithm was first introduced. Three major improvements include the "two-hit" method for hit extension, the ability to generate gapped alignments, and a position-specific, iterated BLAST ("PSI-BLAST") that in many cases is more sensitive to weak but biologically relevant sequence similarities. These improvements are described in detail, for example, in Altschul, "Gapped BLAST and PSI-BLAST: a new generation of protein database search programs," Nucleic Acids Research, 25(17):3389-3402 (1997).
Performance data of the original BLAST implementation indicate that the extension step, where hits are extended to form HSPs, consumed the greatest amount of processing time. The "two-hit" method for hit extension is a refinement on this step, which results in the generation of fewer time-consuming extension steps. Experimental evidence indicates that a typical HSP of interest is much longer than a single word pair, and may therefore comprise multiple hits on the same diagonal and within a relatively short distance of one another. The two-hit method exploits this observation by requiring the existence of two non-overlapping word pairs on the same diagonal, and within a distance A of one another, before an extension is invoked. Any hit that overlaps the most recent one is ignored. Because this method requires two hits rather than one to invoke an extension, the threshold parameter T must be lowered to retain comparable sensitivity. The effect is that many more single hits are found, but only a small fraction have an associated second hit on the same diagonal that triggers an extension. Thus, the great majority of hits may be dismissed after the minor calculation of looking up, for the appropriate diagonal, the coordinate of the most recent hit, checking whether it is within distance A of the current hit's coordinate, and finally replacing the old with the new coordinate. Empirically, the computation saved by requiring fewer extensions more than offsets the extra computation required to process the larger number of hits.
Another method of performing the extension step has been described, for example, in "Multiple sequence alignment using block chaining," Zheng Zhang, PhD dissertation, The Pennsylvania State University, UMI Dissertation Services, Ann Arbor (1996); and Zhang et al., "Chaining multiple-alignment blocks," J. of Computational Biology, 1:217-226 (1994). This method is based on the extension step's similarity to a known class of problems in computer science known as "block chaining," a special case of the classic optimal-path algorithm for directed, acyclic graphs. The method described above adopts a well-known technique of higher-dimensional computational geometry called K-D trees. Generally, K-D trees are used to decompose multidimensional space hierarchically into a relatively small number of cells such that no cell contains too many input objects (see Bentley, Communications of the ACM, 18:509-517, (1975), the entirety of which is incorporated by reference herein). In Zhang, K-D trees are used to decompose the space of possible block chains into regions, thus reducing the block chaining problem to the less computationally intensive problem of chaining regions. The use of K-D trees provides significant computational gains for multiple sequence comparison, i.e., more than two sequences are being compared to each other.
The ability to generate gapped alignments allows for significant improvements in BLAST's performance. The original BLAST program often finds several alignments involving a single database sequence which are statistically significant only when considered together. Overlooking any one of these alignments would compromise the combined result. By introducing an algorithm for generating gapped alignments, it becomes necessary to find only one rather than all the ungapped alignments subsumed in a significant, combined result. This allows the T parameter to be raised, increasing the speed of the initial database scan. One method of generating a gapped alignment employs a heuristic approach which is a simple generalization of BLAST's method for constructing HSPs. The central idea of this approach is to trigger a gapped extension for any HSP that exceeds a moderate score Sg, chosen so that no more than about one extension is invoked per 50 database sequences. Statistical analysis indicates that Sg should be set at approximately 22 bits for a typical-length protein query. A gapped extension takes much longer to execute than an ungapped extension, but by performing very few of them the fraction of the total running time they consume can be kept relatively low. Furthermore, by seeking a single gapped alignment, rather than a collection of ungapped ones, only one of the constituent HSPs need be located for the combined result to be generated successfully. This means that a much higher chance of missing any single moderately scoring HSP can be tolerated. This permits the T parameter for the hit-stage of the algorithm to be raised substantially while retaining comparable sensitivity. For example, T can be raised from 11 to 13 for the one-hit heuristic of the original BLAST implementation.
The iterated application of BLAST to position-specific score matrices, also known as profiles or motifs, allows for database searches that are often much better able to detect weak but biologically significant relationships. One implementation of position-specific, iterated BLAST called PSI-BLAST constructs a position-specific score matrix from the output of a primary BLAST run and uses this matrix as a query for a subsequent BLAST run.
Although several refinements have increased the speed, sensitivity, and specificity of current implementations of BLAST more than three-fold when compared to the original, the exponential rate of sequence database expansion mandates continuous improvement to implementations of the algorithm.
Parallel Processing
One approach for speeding up large database searches is to use parallel processing. High performance parallel computing is accomplished by splitting up large and complex tasks across multiple processors. In a simple example, a sequence database can be subdivided into several parts, with each part assigned to a specific processing unit. The same query can then be run on all processing units simultaneously, with each processing unit having to search only a fraction of the database. In a more complex example, a task is divided into subtasks. For instance, the extension step in BLAST requires an exhaustive examination of alternative chains of HSPs. In this example, the space of possible chains is subdivided into a plurality of subspaces and each subspace is allocated to a separate processor.
While a variety of methods can be used to achieve improved performance on multiple computers, the most common way to organize and orchestrate parallel processing is to write code which automatically decomposes the problem at hand and allows the processors to communicate with each other when necessary while performing their work. In the first example above, if a processor finds a match to the query in its part of the database, it can signal that event to the other processors performing their searches. In the second example above, if a processor finds a new maximum score, it can signal that event so that other processors raise their thresholds.
Most applications of parallel processing usually require some amount of interaction between processors, so they must be able to communicate with each other to exchange information. For example, values for cells on a map may depend on the values of their nearest neighboring cells. If the map is decomposed into two pieces, each being processed on a separate CPU, the processors must exchange cell values on adjacent edges of the map. Similarly, if a sequence alignment is decomposed into several smaller local alignments, each processor handling each local alignment must be able to communicate with processors handling adjacent alignments in order to extend an alignment past its original bounds.
Several contrasting approaches to parallel processing exist. For example, parallel processing can be performed on highly specialized hardware or on commercial off-the-shelf ("COTS") hardware. BLAST and other sequence comparison and database searching algorithms have been implemented in highly-specialized, parallel processing hardware, such as PARACEL'S GENE MATCHER machine. As described in Ullner, U.S. Pat. No. 6,112,288, the entirety of which is incorporated by reference herein, PARACEL'S GENE MATCHER employs a programmable, special-purpose pipeline processing system, which includes a plurality of accelerator chips coupled in series. Each of the accelerator chips includes an instruction processor. Each of the pipeline processor segments includes a plurality of pipeline processors coupled in series. Such specialized hardware can provide significant speedups, especially for dynamic programming algorithms.
In contrast to the specialized hardware approach is the commodity parallel processing approach, which uses inexpensive, commercial off-the-shelf ("COTS") hardware. One popular approach to commodity parallel processing is the Beowulf cluster, described in Becker, et al., Beowulf: A Parallel Workstation for Scientific Computation. Proceedings, International Conference on Parallel Processing (1995); and M. S. Warren, et al., Parallel supercomputing with commodity components; H. R. Arabnia, editor, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA '97), pages 1372-1381, 1997. These publications are incorporated by reference herein in their entireties. A Beowulf-class cluster is a high-performance, massively parallel computer built primarily out of commodity hardware components, running a free-software operating system like Linux or FreeBSD, interconnected by a private, high-speed network. A typical Beowulf-class cluster comprises a plurality of interconnected PCs or workstations dedicated to running high-performance computing tasks. It is usually connected to the outside world through only a single node. A typical Beowulf-class cluster employs a popular method of inter-processor communication called message passing. Popular implementations of message passing include the Parallel Virtual Machine ("PVM") and the Message Passing Interface ("MPI").
Because commodity parallel processing hardware provides substantial performance at reasonable cost, and because exponential database growth requires substantial improvements in database searching techniques, there exists a need to improve the BLAST algorithm to increase its performance on commodity parallel processing hardware.
The invention addresses the above needs and other needs by providing a method and system that utilizes a combined hardware-software system to implement an improved BLAST algorithm that is two to three orders of magnitude faster than previous Blast algorithms executed by single desktop processors. The software component of this system is referred to herein as Paracel BLAST, and the hardware component is referred to herein as the Paracel BlastMachine. In accordance with the techniques taught herein, Paracel BLAST on the BlastMachine can handle genome-scale data sets. Algorithmic improvements and a parallel hardware architecture allow the BlastMachine to solve significantly larger problems than is possible with other techniques. In one embodiment, this system is well-suited for a first pass analysis of a genome, allowing more sophisticated, slower algorithms and also human intervention, at later stages, to fill in gaps that this first pass leaves.
In one aspect, the invention provides structures and methods for performing dynamic database splitting for parallelizing database searching.
In another aspect, the invention provides structures and methods for combining a plurality of queries into a single database search.
In another aspect, the invention provides structures and methods for efficient linking and extending High-scoring Segment Pairs to yield longer matches between a query sequence and a database sequence.
In one specific embodiment, the present invention is directed to a method for comparing a plurality of query sequences against a sequence database comprising the steps of: (a) combining said plurality of query sequences into a combined query sequence; (b) determining a plurality of subdivisions of said database; (c) performing a plurality of searches, wherein each search comprises a comparison of said combined query sequence against one of said plurality of subdivisions of said database, producing a plurality of word matches; (d) extending the length of plurality of word matches produced in step (c), producing a plurality of High-scoring Segment Pairs; (e) combining said plurality of High-scoring Segment Pairs; and (f) producing a plurality of reports, each report representing the highest scoring matches for one of said plurality of query sequences.
The plurality of sequences can be combined into a combined query sequence by any suitable method. For example, in step (a) of the present method, a plurality of sequences are combined into a combined query sequence by storing said plurality of sequences in a query lookup table and indexing each of said sequences with a query number to link each said sequence to a respective query number. The combining process can be controlled or monitored using any suitable parameters, e.g., a length parameter. More specifically, a plurality of sequences can be stored in a query lookup table until the amount of data stored in said table reaches a predetermined limit. In another example, in step (a) of the present method, a plurality of sequences can be combined by constructing a hash of multiple queries at the same time.
The database can be divided into a plurality of subdivisions by any suitable method. For example, the step of determining a plurality of subdivisions of the database can comprise specifying the size of said database in number of bases and the number of sequences in said database to calculate a statistically significant value for results produced by searching said databases. In other examples, the database can be divided into a plurality of subdivisions by making one or more of the following modifications to the basic BLAST algorithm: (i) at least one of the statistical parameters of the basic BLAST algorithm is adjusted to generate correct partial results; (ii) at least one of the input/output routines used in the basic BLAST algorithm to access the database is modified to support accessing a subset of the database; (iii) a plurality of memory images of intermediate results is produced; and/or (iv) the memory images are recombined to produce a single merged BLAST report. In a specific example, the basic BLAST algorithm is adjusted to specify both the size of the database and the number of sequences in the database to calculate the statistical significance of the results produced by searching the database. In another specific example, a command-line argument (−z) is used to specify the size in bases of the overall database and a command-line option (−s) is used to specify the number of overall sequences in the database. The values for the −z and −s parameters can be automatically calculated, if they are not otherwise provided, based on the overall size of the subsetted database. The database can also be divided into a plurality of subdivisions by specifying a first ordinal ID (x) to indicate a start of a subject of said database, and specifying a second ordinal ID (y) to indicate an end of said subset of said database, wherein said first ordinal ID ranges from 0 to N−1, wherein N is the number of sequences in the database. The database can be subdivided into pieces of any suitable sizes. For example, the database can be subdivided into pieces that are small enough to fit into RAM on the nodes.
The length of plurality of word matches can be extended in step (d) of the present method using any suitable method. For example, the extending step can comprise the steps of: (i) evaluating a set of the High-scoring Segment Pairs to determine the highest-scoring chain in said set according to a first criterion, wherein said chain comprises a subset of said set of High-scoring Segment Pairs; (ii) removing said chain from said set of High-scoring Segment Pairs; and (iii) repeating said steps (i) and (ii) until said set of High-scoring Segment Pairs is empty. Preferably, the evaluating step (i) can comprise the step of determining a subset of said set of High-scoring Segment Pairs which does not require recalculation according to a second criterion. In another example, the length of the plurality of word matches is extended using link_hsps( ). The length of the plurality of word matches can be extended on separate processors. Alternatively, the length of plurality of word matches can be extended on the same processor used to perform the database search.
The plurality of High-scoring Segment Pairs can be combined in step (d) of the present method using any suitable method. For example, the plurality of High-scoring Segment Pairs can be combined using a "pbmerge" program.
The present method can be conducted on any suitable hardware. For example, the present method can be conducted on commercial off-the-shelf ("COTS") hardware. Preferably, the present method can be conducted on a Beowulf-class parallel processing architecture.
The present method can be used to conduct searches for any query sequence in any suitable sequence database provided that the query sequence is compatible with at least some sequences contained in the database. However, although preferably in some circumstances, it is not necessary that the query sequence is compatible with all sequences contained in the database. For example, a protein sequence can be used as a query sequence to conduct a search in a database that contains protein sequences as well as nucleic acid sequences. Similarly, nucleic acid sequence, such as a DNA or an RNA sequence, can be used as a query sequence to conduct a search in a database that contains nucleic acid sequences as well as protein sequences.
The present method can be used to conduct searches in any suitable sequence databases such as databases comprising genomic, cDNA, EST sequences or a combination thereof. The present method can be used to conduct searches in a public database, e.g. GenBank, or a subscriber-only database.
In another specific embodiment, the present invention is directed to a method for conducting sequence searches in a database with a BLAST algorithm using the following steps: (a) compile a list of high scoring words of length w from a query sequence; (b) for each sequence in the database, scan for word hits with scores greater than a threshold T; and (c) for each word hit, extend it in both directions to form a High Scoring Pair ("HSP") of score greater than or equal to S, wherein the improvement comprises one or more of the followings: (i) combining a plurality of query sequences into a combined query sequence before conducting said search; (ii) determining a plurality of subdivisions of a database before conducting said search; (iii) restructuring coding so that whenever possible, a hash table stays in the processor's cache, rather than bouncing back and forth between processor and memory; and/or (iv) dividing query sequence that equals to or is longer than a megabase (one million bases or base pairs) into smaller pieces before conducting said search, e.g., by dividing said query sequence into overlapping pieces and running each piece separately in the search. Preferably, the query sequence is divided into smaller pieces by the following steps: a) dividing said query sequence into a plurality of overlapping sequences; b) removing overlapping portion from said overlapping sequences so that each overlapping portion is contained in only one overlapping sequence; and c) detecting whether the removed portions contain any HSPs that span said entire overlapping portion and if such HSPs are detected, finding the original hit that led to said HSP and extending said HSP in the context of the undivided query sequence. The query sequence can be divided into smaller pieces of any suitable sizes, e.g., about 10 kilobases (thousand bases or base pairs).
In still another specific embodiment, the present invention is directed to a system for conducting sequence searches in a database, which system comprises a manager node and a plurality of worker nodes, wherein said manager node is operatively linked to a client station and each of said worker nodes, and said system is capable of conducting sequence searches in a database according any of the above-described methods. In one example, at a hardware level, the manager module includes a manager node having a dual-cpu motherboard, RAM, disk, and network cards. Other nodes, e.g., worker nodes, include similar hardware, usually minus the disk. In one preferred example, the manager node executes a manager "daemon" (persistent process) software that runs on the manager node, while worker daemons run on worker nodes. The manager daemon is responsible for accepting job requests from client processes, which typically run on client workstations, queuing them, partitioning them into sub-jobs or tasks, scheduling the tasks, and assigning them to the worker daemons. The worker daemons request sub-jobs from the manager daemon, execute those sub-jobs, and return results to the manager daemon.
A detailed description of each of these elements and the operation of the algorithm is provided below. All references cited herein are incorporated by reference in their entirety.
For clarity of disclosure, and not by way of limitation, the detailed description of the invention is divided into the subsections that follow.
Unless defined otherwise, all technical and scientific terms used herein have the same meaning as is commonly understood by one of ordinary skill in the art to which this invention belongs. All patents, applications, published applications and other publications referred to herein are incorporated by reference in their entirety.
As used herein, "a" or "an" means "at least one" or "one or more."
For the purposes of this invention, unless otherwise specified, "BLAST" refers to an algorithm based on the Basic Local Alignment Search Tool algorithm described in Altschul et al., J. Mol. Biol., 215:403-410 (1990), the entirety of which is incorporated by reference herein. "NCBI BLAST" refers to version 2.1.2 of the National Center for Biotechnology Information's implementation of the BLAST algorithm, which is well-known in the art.
As used herein, "node" refers to a distinct spot or place in a computational tree or system. A node can be a CPU, a processor or a microprocessor or a functional portion thereof or a combination thereof. For example, in the context of a computing cluster, a node can be a single computer, consisting of one or more processors (CPUs) and a single shared collection of other hardware such as memory (RAM), or network card(s), etc.
As used herein, "link_hsps" refers to a subroutine in NCBI blast tool. For each query sequence and each database sequence, the routine link HSPs computed in an earlier stage between these two sequences to evaluate how similar the two sequences are. Base on the result of link_hsps, the programs decide if a gap alignment will be computed for this sequence pair.
Query Packing
In BLAST, each query search of a sequence database requires computational overhead to set up the search. Specifically, a lookup table needs to be constructed for the query. By combining several queries into one search, the amount of computational overhead per query is reduced, and the overall throughput of query processing is increased. In one embodiment, the BLAST algorithm is modified to add the capability to pack multiple query sequences into a single scanning pass of the database, thus decreasing processing time for multiple small queries while producing results that are identical with the results produced by NCBI BLAST on the same input queries. Specifically, the query lookup table is modified to contain information from several queries, along with the necessary indexing, called "query number," to link the information to its respective query.
It is important that the results of a combined query be identical to the results produced by individual searches of its constituent queries. To ensure that identical results are produced, a hash table generation is combined with scanning for multiple queries by assigning an ordinal index to each query and adding it to the hash table entries. Additionally, a separate search structure is maintained for each query for performing all post-scanning phases, including diagonal calculations such as ungapped extension, gapped extension, and alignment.
In this embodiment, a length parameter is used to determine how much query data can be combined. In prior art implementations of BLAST, a main loop received queries as input and processed one query per iteration. In this embodiment, the main loop is modified to have an inner loop that combines queries until the aggregate length of combined queries reaches or exceeds the length parameter, and performs the database search with the combined queries. The results of the combined database search comprise all of the significant word matches in all of the combined queries. The next step involves extension of these words into HSPs. The diagonal processing in this step is query specific, so all diagonal calculations are performed independently per query inside this inner loop.
In one preferred embodiment, for each query sequence Q and each database sequence D, the method of the invention performs the following processing steps.
1. Find all local alignments
2. For the top n highest scoring database sequences D, report all alignments
The BLAST specifics come at the inner step—finding the alignments. The key to the BLAST heuristic is that a statistically significant alignment is likely to contain a high scoring pair (HSP) of aligned words. The algorithm first searches for short exact matches (default length 11 for nucleotides, 3 for protein) between query sequence and database sequence. Such matches are called hits. These hits are then extended, first without gaps, then with gaps, and those HSPs that are above a given threshold are returned. The full extension step is very computationally intensive, so BLAST avoids performing unnecessary computation by only calculating full alignments for those pairs that are statistically likely to be HSPs.
One part of the algorithm that is optimized in Paracel BLAST is the way in which hit generation occurs. The algorithm for hit generation is:
1. Pre-process query, making a hash table of (n-mer, position in query where n-mer occurs).
2. Go through the database sequence and, for each n-mer, look up that n-mer in the hash table. Any positions at that index of the table are hits.
For example, suppose the query is MSLPT. Then the 3-mers are 1) MSL, 2) SLP, and 3) LPT. The hash table is shown in Table 1. Thus, a database sequence containing SLP, for example, would generate a hit at query position 2.
The hash table for the query MSLPT. For each 3-mer of amino acids
(AAA . . . YYY), the table contains entries for those positions in the
query where that 3-mer occurs. For example, MSL occurs at position 1.
. . .
. . .
. . .
. . .
One of the most "expensive" (memory-consuming) data structures in the BLAST algorithm is the hash table mentioned above. At a very high level, the algorithm looks like this:
1. Populate hash table;
2. For each hit in the hash table, do more processing.
The NCBI BLAST code does not do any special management of this hash table. Paracel BLAST has re-structured the code so that whenever possible, the hash table stays in the processor's cache, rather than bouncing back and forth between processor and memory. This involves some encoding of values in the table to decrease memory usage and hence table size, so that the table fits into the cache. Since cache accesses are significantly faster than memory accesses, this results in a substantial speedup.
Dynamic Database Splitting
In the prior art, a large database to be searched could be statically split into several smaller databases. However, such a setup would require an entire BLAST search to be performed on each of the smaller databases, with no statistically valid way to combine the results of these independent searches. In one embodiment of the invention, the BLAST algorithm is modified to support splitting a search against a single large database into multiple searches against subsets of that single database without creating multiple smaller databases to represent the subsets. In this embodiment, the results are automatically recombined to produce a single BLAST report that is biologically equivalent to the report produced by searching the entire database without splitting. This modified method, referred to herein as "dynamic database splitting," requires modification to the basic BLAST algorithm in four separate areas: First, the statistical parameters need to be adjusted to generate correct partial results. Second, the input/output routines used to access the database need to be modified to support accessing a subset of the database. Third, a memory image of intermediate results needs to be produced. Fourth, these memory images need to be properly recombined to produce a single merged BLAST report.
BLAST uses the size of the database and the number of sequences in the database to calculate the statistical significance of the results produced by searching the database. To arrive at consistent results, the size in bases and number of sequences of the overall database(s) being searched must be specified. Prior art implementations of BLAST provided a command-line argument (−z) to specify the size in bases of the overall database to be used in statistical calculations, but did not provide a corresponding way to specify the number of overall sequences. In one embodiment of the invention, a new command-line option (−s) was added to specify this number, which is added to the options data structure that is referenced by the code during the search. In this embodiment, the code that calculates statistical parameters uses the value of the −s option in preference to the actual number of sequences contained in the overall database. In a further embodiment, the values for the −z and −s parameters are automatically calculated if they were not otherwise provided, based on the overall size of the subsetted database.
In one embodiment, the BLAST algorithm was modified to search a subset of a database. In a further embodiment, a subset of the database can be specified using the following nomenclature: "database#x-y", where "database" is the database name, x is the first ordinal ID ("OID") to include in the search, and y is the last OID to include in the search. In this embodiment, OID ranges from 0 to N−1, where N is the number of sequences in the database. In yet a further embodiment, a subset of the database can be specified using the following nomenclature: "database#x-y#n", where n is the number of bases in the specified subset. If n is not specified then the size of the entire database is used—this number only affects the sizing information in the report.
In this embodiment, NCBI BLAST's code was modified to reflect a basic change in the notion of a memory-mapped file in the readdb subroutine, which includes the indexfp, headerfp, and sequencefp files in the basic readdb data structure ReadDBFILE. Prior art implementations of BLAST only allowed an entire file to be mapped using the mmap(2) UNIX system call or equivalent (by calling Nlm_MemMapInit). In this embodiment, it is now possible for up to three ranges of a file to be mapped, for the header, sequence, and ambiguity sections of the index file, respectively. In this embodiment, when an index file is read in readdb_new_internal, it is initially opened without memory mapping at all. Once the number of sequences in the file is determined, the index file is closed and re-opened with two (protein) or three (DNA) ranges for memory-mapping specified. If a range of OIDs is being used, the subranges of the header and sequence files are calculated and stored in the ReadDBFILE structure by readdb_new_internal. Later they are used to map only a range of the files when they are opened in ReadDBOpenMHdrAndSeqFiles.
In one embodiment, the BLAST algorithm is modified to produce intermediate results as output instead of a final BLAST report. The intermediate results are a serialized copy of the memory image of the dynamic data structures at the point in the blastall main loop just prior to generating the alignments. In this embodiment, the dynamic data structures at this point are traversed and each memory block is stored along with embedded pointer information converted from absolute RAM addresses to relative indexes into the transcribed memory blocks. In this embodiment, no text output is produced at this stage.
In this embodiment, a program called "pbmerge" was written to read the intermediate results from multiple pieces of a large database, as described above, and to transcribe them into equivalent memory images of each by allocating dynamic memory for the memory blocks, and converting embedded memory references back from relative indices to absolute RAM addresses. The pbmerge program then combines the multiple intermediate results into a single set of results, sorts the combined results by score, and discards the lowest scoring alignments, resulting in the requested number of best matches. Finally, pbmerge executes the trailing part of the blastall main loop that was short-circuited above to produce a single merged BLAST report as output.
Linking High-Scoring Segment Pairs
As described in the Background, experimental evidence has demonstrated that the majority of computation time in BLAST is taken by extending hits, and especially in performing gapped extensions. In a typical implementation, this step occurs in a function named link_hsps( ). Even with the improvements described in the Background, a significant amount of BLAST's computational time is still spent in link_hsps( ). The function and context of link_hsps( ) is described as follows: Given a query sequence and a database, for each sequence S in the database, determine a set of HSPs H for the sequence S. The link_hsps( ) function then estimates the statistical significance of the set of HSPs H for the sequence S, and adds the sequence S to a list of most significant matches if the statistical significance exceeds a predetermined threshold. Once all of the sequences have been processed, BLAST then performs a gapped extension on the most significant matches and outputs the alignments.
In more detail, link_hsps( ) implements the following algorithm: (1) Find the highest-scoring chain C from the set of HSPs H; (2) compute the significance for C; (3) remove C from H; and (4) repeat until H is empty. The score for a chain C is calculated as follows: Given a chain C consisting of an ordered set of k HSPs H1, H2, . . . , Hk, where Hi precedes Hi+1, then:
Where score(Hi) is the score of that HSP and connect(Hi,Hi+1) is the penalty to connect two HSPs. Computing the maximum-scoring chain C can be performed in a computationally efficient manner based on the following observation: Let S(H) be the highest scoring chain ending at the HSP H. It follows that for the set of all H′ preceding H in the chain,
S(H)={hεH′; max(S(h)−connect(h, H))}.
In other words, the highest score of the chain ending at H is a maximum of the scores of its preceding subchains minus their respective connection penalties. It follows that if all the values S(h) are already computed, then S(H) can be readily computed. In general, for a chain of k HSPs H, there could be O(k) HSPs preceding H. This dependency is illustrated in FIG. 1. In
Currently, a typical implementation of BLAST uses two connection functions, known as the large gap criterion and the small gap criterion. The large gap criterion allows large gaps to be formed, and so it sets its connection penalty to zero. The small gap criterion disallows gaps larger than a predetermined constant A. The small gap criterion sets its penalty to zero for gaps equal to or smaller than A, and to negative infinity for gaps larger than A. Current implementations require O(k) time to compute each S(h), and O(k2) time to find the highest-scoring chain ending at H. To find all chains takes up to O(k3) time. Because k grows linearly with query length, and the rest of the BLAST algorithm grows linearly with query length for a fixed database, it follows that link_hsps( ) will become the run-time bottleneck for long query sequences. As discussed elsewhere in this application, one embodiment of the invention employs "query packing," which involves the concatenation of several queries, thus increasing query length. Experimental evidence has demonstrated that for a 1 Mb query, up to 80% of computational time can be spent executing the link_hsps( ) function. In a set of HSPs H, elements with the same starting element are said to belong to the same class. As described above, one step of link_hsps( ) is to remove the highest-scoring chain C from the set of HSPs H. Because the calculation of a chain's score is performed in a manner depending on preceding points in the chain, as described above, removal of C from H requires that all C-dependent elements remaining in H be recomputed. By definition, all HSPs in a chain belong to the same class. When a chain is removed, all the remaining elements of that class need to be recomputed. In one implementation of BLAST using two separate gap criteria, each element in H belongs to two separate classes; the best chain for one criterion may contain elements from different classes in the other criterion. In current implementations, removal of the best chain of one criterion requires that all classes of the other criteria need to be recomputed. In one embodiment of the invention, the performance of link_hsps( ) is improved by avoiding this sort of recomputation.
Given a set of HSPs H, two gap criteria, and an element h in H, denote link1(h) be the previous HSP to h in the highest-scoring chain according to criterion 1 and link2(h) to be the previous HSP to h in the highest-scoring chain according to criterion 2. The forest F1 is defined as the set of subtrees with link1(h) as their parent. Similarly, the forest F2 is defined as the set of subtrees with link2(h) as their parent. In general, if an element h in F1 is removed, only the HSPs in the subtree rooted at h need to be changed. Similarly, if a chain from F1 is removed, by definition all HSPs in the chain are in one tree of F1; also, because the root of that tree is also removed, the remaining HSPs in that tree need to be recomputed. However, the set of HSPs that need recomputation are not necessarily in the same tree for F2. In one embodiment of the invention, instead of the entire chain being removed all at once, the individual elements of the chain to be removed are removed individually, as well as the subtree of the element removed.
After recomputation, link_hsps( ) determines the best chains in the new tree structure. A naive approach to this process would involve visiting every HSP in the trees that have changed. This approach is unnecessarily time consuming because experimental evidence has demonstrated that the number of HSPs needing recomputation tend to be a small fraction of those changed. A more efficient approach employs a heap for each tree in the forest, based on the score S(h) for each HSP. The heap allows the tree's highest-scoring chain to be determined in O(1) time. Because only the HSPs that need recomputation are visited, the total running time is O(rm0.5+r log m) in the worst case, and O(r log m) in practice, where r is the number of recomputations and m is the number of HSPs. Experimental evidence indicates that r is close to m1.5 in practice.
In one example, a 1.1 Mb query was run against a 650 Mb sequence database. The implementation of BLAST available from the National Center for Biotechnology Information ("NCBI"), version 2.1.2 required 17 hours to run. In contrast, an implementation of BLAST employing the improvements to link_hsps( ) described above finished in less than 3 hours under identical conditions.
As mentioned above, operations on the hash table—populating it and looping over it—consume a significant amount of time. This is particularly true for short queries, where only a few entries in the table will be populated. In fact, one reason that MegaBlast was developed to provide faster nucleotide vs. nucleotide searches for many small queries as described in Zhang, Z., Schwartz, S., Wagner, L. and Miller, W., A greedy algorithm for aligning DNA sequences. Journal of Computational Biology, 7(1-2):203-214 (2000), the entirety of which is incorporated by reference herein. There are also several scripts available on the web, for example, that "pack" together queries, for example, putting "don't cares"—Ns for nucleotide, Xs for amino acid—between queries, running a single search, then post-processing the results to correct for offsets of the original queries within the constructed query. For example, the queries ACTG and GCGCG might be packed as ACTGNNNNNNNNNGCGCG. The point of the don't cares is to make it unlikely that a hit would occur across queries. The problem with MegaBlast and these scripts is that accuracy is lost—the statistics mean different things for a single long query and many short queries.
In accordance with one preferred embodiment, a Paracel BLAST Query Packing Algorithm maintains statistical validity with improved speed. In one embodiment, the Paracel BLAST Query Packing Algorithm works by constructing the hash of multiple queries at the same time. Instead of the hash table containing position only, it contains an ordered pair of (query number, position in query). For example, Table 1 contained the hash table created when a query Q1=MSLPT was hashed. Suppose additionally, the queries Q2=ALPTV and Q3=VMSLIC are hashed. The resulting hash table is shown in Table 2.
The query-packing hash table for the queries MSLPT, ALPTV,
and VMSLIC.
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
This optimization involves modifications to the way the hash table is populated and the way hits are read out of the hash table—all subsequent processing on hits remains the same. The key is to populate the hash table with data from a packed pipeline of several queries, enough so that the hash table will be relatively full without being overcrowded. This improves performance of sets of small queries significantly. Note that unlike MegaBlast, this technique works on amino acids as well as nucleotides, so Paracel BLAST is able to run faster searches in a statistically correct way for all BLAST variants.
Implementation on Parallel Architecture
One embodiment, an implementation of the BLAST algorithm incorporating the improvements described above is to run it on a Beowulf-class parallel processing architecture. In this embodiment, the machine performs database searches at a high rate of throughput. As queries are received, they are packed into a combined query until the size of the combined query reaches a predetermined threshold. The database to be searched is partitioned, and each processor on the machine handles the combined query search over a specific partition of the database. In a preferred embodiment, the database is dynamically partitioned so that each processor completes its search in roughly the same amount of time. The output of each database search comprises a plurality of hits, along with information linking each hit to its query in the combined query. Because the diagonal calculations for each hit are query-specific, each query's hits are then extended separately using link_hsps( ). In one embodiment, each query's hits are processed on a separate processor. In an alternate embodiment, each query's hits are extended on the same processor used to perform the database search. When all of the combined query's hits for a partition of the database have been found and extended, that partition's intermediate result is stored. Finally, the intermediate results for all database partitions are recombined and a final BLAST report is produced for each query in the combined query. In one preferred embodiment, the BlastMachine is a Beowulf-style Linux cluster, consisting of a manager node and multiple worker nodes (see FIG. 2). Each node runs Paracel BLAST, an optimized version of NCBI BLAST. The manager responds to client BLAST requests by splitting the job into smaller pieces, assigning those pieces to workers, collecting the results, and returning them to the client. Much of the complexity of the system is in the splitting and scheduling aspects, which are discussed in further detail below. BlastMachines with as few as one cpu and as many as 92 CPUs have been built. In one embodiment, each worker node is a 2-CPU Pentium III™ system.
Two performance-related problems in distributing jobs are 1) load balancing and 2) caching. To illustrate load balancing, suppose a job that takes 100 minutes on a single processor is distributed among 50 processors. If the load of each processor is the same, the job takes 2 minutes. Alternatively, suppose 49 processors receive pieces requiring 1 minute, and the final processor receives a piece requiring 51 minutes. Then the total problem takes 51 minutes, roughly half the time it required on a single CPU. Because of poor load balancing, the job may not come any where near the 50 times speedup expected based on number of processors alone. To improve this kind of pathological case, it is desirable to divide a job into as many pieces as possible. Since it is not known a priori which pieces will take the most time (a significant fraction of the time depends on the number of hits, which is not knowable without running the search), dividing into more pieces will allow faster pieces to finish sooner, and those processors may then be used for the remaining pieces. In the limit of small pieces, one might hope to break a job into such small pieces that one may achieve the actual speedup equal to the number of processors. In practice, however, there is some small amount of overhead associated with each piece, so there is a limit to how fine-grained the division can be.
A straightforward query splitting technique is to split each query into its own separate sub-jobs. Each such piece can then be scheduled independently and put on a different processor, without having to adjust statistics in subsequent steps of the BLAST algorithm. It turns out that independently scheduling each query piece—although correct—is not optimal, because it lessens the optimization provided by the query packing algorithm above. That algorithm achieves a speedup whenever multiple queries can be packed together. So the Paracel Blast manager node does some balancing—on the one hand it wants to partition as finely as possible to achieve better load balancing and utilize parallelism more efficiently; on the other hand, it wants to keep multiple queries together to optimize the speed of each piece. Depending on one's emphasis on latency or throughput, and depending on the specifics of the data involved, different strategies can be used. These strategies are discussed in further detail below.
As discussed above, in the same way Paracel Blast splits queries, it can split databases. In one embodiment, for each database D and each query Q, the Paracel BLAST algorithm finds alignments between Q and D. There is, however, a catch. To find the alignments, a statistical cutoff is used that depends on the size and number of sequences in the entire database. In one embodiment, an enhanced BLAST code allows a process manager algorithm to pass that information to each query piece. A second part of the algorithm merges all database pieces corresponding to the same query piece. For each query Q, the algorithm reports the top n database sequences in function called MERGE(D1, D2, . . . , Dm) described in further detail below. Unfortunately, this merging may sometimes produce sort orders different than those of native NCBI BLAST, as alignments with the same score are not sorted deterministically. The quality of results is the same, however, as is the statistical validity.
In one embodiment, the merge procedure is as follows: given database pieces D1, D2, . . . , Dm, and the top n alignments for each database piece, find the top n alignments overall. In a preferred embodiment, query and database splitting are mutually independent, so both optimizations can be applied simultaneously.
One benefit of database splitting is that databases can be split into pieces that are small enough to fit into RAM on the nodes. This provides two benefits:
1. The BLAST algorithm is coded in such a way that it is significantly faster if the database can stay in memory, rather than accessing it from disk or across the network, and
2. Moving databases around—particularly large ones—is expensive, so the manager tries to assign the same database piece to the same processor, thus achieving a significant speed improvement.
Database caching also allows a super linear speedup. Essentially, a job that has to load a database from disk (because it is too large to fit into memory) can be broken into n pieces, where each piece is small enough to fit into memory. The total time for a single CPU is: DB disk access+computation. For N CPUs, the total time becomes: 1/N�(DB RAM access)+1/N computation. Since RAM access is much faster than disk access, the total time on N CPUs is less than 1/N the time for one CPU, possibly much less, and the speedup may be super-linear.
This effect is particularly striking on large jobs broken into many pieces—the first pieces run at the same speed as would be expected based on naively dividing by the number of processors. Subsequent pieces can use the cached database and are much faster. So the overall job (for longer jobs) tends toward the RAM access time, not disk access time. Note that this occurs only because the Paracel Blast manager attempts to assign different sub-jobs that use the same database piece to the same processor.
It is understood that the splitting algorithms described above apply to a set of query sequences, or combined queries, and a database comprising of multiple sequences. Individual sequences are typically not split. With available genomic sequences, however, individual sequences may be many megabases long. In one embodiment, to handle such long individual sequences, Paracel Blast uses an algorithm called Query Chopping.
A na�ve way to do query chopping is to manually split a long sequence into overlapping pieces and run each piece separately as shown in FIG. 3. This could even be done by a script without access to the internals of BLAST. Paracel Blast's query chopping is somewhat more sophisticated, in that it corrects for several potential problems in the overlap zone.
Referring to
One overriding design goal is to present the same results we would obtain if there were no chopping and the entire sequence were treated as a whole. As shown in
The Paracel BLAST query chopping algorithm detects such HSPs and goes back to the original hit that led to that HSP. The original hit is extended into an HSP in the context of the unchopped query. Note that although this operation is expensive, it is exceedingly rare—it only occurs when there is an HSP that fully spans the overlap. In one preferred embodiment, Paracel BLAST uses a default overlap of 10 kilobases, so the time to recalculate these is typically very small compared to the savings gained by being able to split the query more finely and farm it out to multiple processors.
In one embodiment of the invention, Paracel BLAST includes a manager module, which partitions a job into pieces, farms each piece out to the best available worker (e.g., processor or CPU), then recombines pieces. In performing this management function the manager module considers certain competing constraints. For load balancing reasons, it would be optimal to partition into as many pieces as possible. For query chopping and database splitting, which have a merge step, excessive partitioning would require more merges and hence be inefficient. For query splitting, excessive splitting would ruin efficiencies gained by query packing. Partitioning should also take into account the number of machines—partitioning into too few pieces would leave machines idle, whereas over-partitioning—partitioning into more pieces than machines—might be desirable to improve load balancing. Additionally, there is an issue of moving data from disk over the network to the processors of the workers. For sufficiently large databases, data movement time is significant and may dominate computation time. In such cases, it may be better to partition into fewer pieces. Paracel BLAST uses a set of heuristics to do a good (but not perfect) job of handling these scheduling problems.
The improvements mentioned above may be viewed independently or collectively. In the examples discussed below all BlastMachine nodes consisted of dual Pentium III™ processors running at 933 MHz with 2 GB of RAM, unless otherwise specified.
Code Optimization, Hash Table Caching, and Query Packing
To demonstrate the power of code optimization, data structure optimization, and query packing, a query data set of 50,000 25-mers (i.e., 1,250,000 bases total) taken from human chromosome 22 was run against the human reference sequences database from NCBI (10,239 sequences, 24,300,774 bases). On a 1 CPU Pentium III™ system running at 933 MHz, NCBI BLAST took 3 hours 16 minutes. On the same hardware, Paracel BLAST took 22 minutes 35 seconds—an 8.7 fold speedup.
Query Splitting
Query splitting by itself only improves latency, it does not improve throughput. However, it plays a role in all of the system benchmarks discussed below.
Database Splitting
One eighth of the human transcript database from Baylor (10,610 sequences containing 5.6 megabases) was run against the human ensemble database (30,445 sequences containing 4.4 gigabases). This search required substantial amounts of memory. In fact, NCBI BLAST 2.1.2, run on a single CPU Pentium 3 system runs out of memory and fails after 2 weeks. On a large memory, 4 CPU Alpha ES40 system, NCBI BLAST 2.1.2 runs in 214 hours and 14 minutes (almost 9 days). On a 32 CPU BlastMachine, the same search runs to completion in a mere 3 hours 17 minutes.
Query Chopping
To illustrate the power of query chopping, all the human ESTs were aligned to chromosome 22. The EST database used contains 3.7 million sequences, totaling 1.8 gigabases. Chromosome 22, obtained from the Sanger Centre, contains a single sequence of 34.6 megabases. A problem of this size cannot be run under NCBI BLAST on a typical Linux PC—it immediately runs out of memory and dies. Using Paracel BLAST's query chopping, the search ran on an 8 CPU BlastMachine in 19 minutes, 43 seconds.
C. Elegans Proteins versus NR
Several problems of interest cannot be completed in a reasonable time on conventional computers. For example, the Wormpep19 database, containing 19,105 sequences containing 8.3 million peptides from C. elegans, was searched against the NR database (non-redundant protein sequence database from NCBI). NR contains 582,290 sequences containing 183 million peptides. Of particular note is that one of the Wormpep sequences is a single 25,000-peptide protein. On a 1 CPU system, NCBI BLAST failed after 4 days (presumably due to memory issues related to sequence size). On a 32 CPU BlastMachine with Paracel BLAST, the same search ran to completion in 1 hour, 57 minutes.
All Human ESTs vs. All Chromosomes
One of the largest searches run to date was the alignment of all human ESTs with all human chromosomes. As above, the EST database used contains 3.7 million sequences, totaling 1.8 gigabases. The complete set of human chromosomes, obtained from UCSC, contains 3,626 sequences, totaling 3.3 gigabases. This search would not be possible without query chopping, and would be inordinately slow without all the other optimizations covered above. With Paracel BLAST on a 48 CPU BlastMachine, it ran to completion in 85 hours, 49 minutes. At present, there is not enough annotation of most of the human chromosomes to allow us to analyze the results in detail, as is being done with the ESTs and chromosome 22.
The Paracel BlastMachine is a system for homology search on a genomic scale. Rather than focusing on improving the sensitivity and selectivity of homology searching, it seeks to do a reasonably good job faster and for larger data sets than has been possible before. Paracel BLAST incorporates many individual optimizations that split problems and farm them out to as many nodes as possible. Each node runs code optimized to use the CPU more efficiently. The combination of query splitting, database splitting, query chopping, query packing, database caching, hash table caching, and assembly optimizations make the BlastMachine two to three orders of magnitude faster than a desktop computer (exact numbers depend on the problem and the extent to which these optimizations can be exploited).
All of the algorithmics are transparent to the user. A user submits a BLAST job through a GUI or command line, and the software automatically applies all applicable optimizations without further user intervention. The BlastMachine solves genomic-scale problems in hours, not weeks (for example, comparing a fraction of the human transcript database to the human ensemble database took just over 3 hours on a BlastMachine, compared with 9 days on an Alpha system running NCBI BLAST 2.1.2). Furthermore, Paracel BLAST partitions certain jobs automatically into manageable pieces, and hence runs searches to completion that fail on other architectures (for example placing all human ESTs on chromosomes). As ever more genomic scale data sets become available, we believe this sort of optimized tool will become increasingly useful for large-scale data analysis and mining.
The invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. The foregoing embodiments are therefore to be considered in all respects illustrative, rather than limiting, of the invention described herein. The scope of the Invention is thus indicated by the appended claims, rather than by the foregoing description, and all variants that fall within the meaning and range of equivalency of the claims are therefore intended to be embraced therein. Furthermore, it is contemplated that the improvements described herein are not limited to sequences of biological information such as DNA and peptides, but can be applied to string searches of any kind.
|Cited Patent
|Filing date
|Publication date
|May 19, 1998
|Aug 29, 2000
|Paracel, Inc.
|Dynamic configurable system of parallel modules comprising chain of chips comprising parallel pipeline chain of processors with master controller feeding command and data
|Oct 20, 1998
|Apr 24, 2001
|Incyte Pharmaceuticals, Inc.
|System and method for a precompiled database for biomolecular sequence information
|Jun 27, 2000
|Jul 16, 2002
|Pioneer Hi-Bred International, Inc.
|Data processing of the maize prolifera genetic sequence
|Jul 28, 2000
|Oct 22, 2002
|Agy Therapeutics, Inc.
|Techniques for facilitating identification of candidate genes
|Mar 22, 2001
|Feb 10, 2004
|Turbo Worx, Inc.
|Method and apparatus for high-performance sequence comparison
|<http://www.ncbi.nlm,.nih.gov/Genbank/genbankstats.html> (visited Jul. 30, 2002).
|Altschul et al. "Basic Local Alignment Search Tool" J. Mol. Biol. 215(3):403-410 (1990).
|Altschul et al. "Basic Local Alignment Statistics" Methods in Enzymology 266:460-480 (1996).
|Altschul et al. "Gapped BLAST and PSI-BLAST: New Generation of Protein Database Search Programs" Nucleic Acids Research 25(17):389-3402 (1997).
|Benson et al. "GenBank" Nucleic Acids Research 28(1):15-18 (2000).
|Bentley. "Multidimensional Binary Search Trees Used for Associative Searching" Communications of the ACM 18(9):509-517 (1975).
|Eddy. "Profile Hidden Markov Models" Bioinformatics 14(9):755-763 (1998).
|Henikoff et al. "Amino Acid Substitution Matrices from Protein Blocks" Proc. Natl. Acad. Sci. USA 89:10915-10919 (1992).
|Henikoff et al. "Performance Evaluation of Amino Acid Substitution Matrices" Proteins 17:49-61 (1993).
|Zhang et al. "A Greedy Algorithm for Aligning DNA Sequences" J. of Computational Biology 7(1-2):203-214 (2000).
|Zhang et al. "Chaining Multiple-Alignment Blocks" J. of Computational Biology 1:217-226 (1994).
|Citing Patent
|Filing date
|Publication date
|Oct 5, 2004
|May 1, 2007
|Unisys Corporation
|Saving and restoring an interlocking trees datastore
|Jan 16, 2004
|Mar 4, 2008
|Unisys Corporation
|Saving and restoring an interlocking trees datastore
|Dec 16, 2004
|Mar 25, 2008
|Unisys Corporation
|Method and apparatus for interface for graphic display of data from a Kstore
|Jun 10, 2005
|Jun 17, 2008
|Unisys Corporation
|Data aggregation user interface and analytic adapted for a KStore
|Apr 7, 2005
|Aug 5, 2008
|Unisys Corporation
|Facilitated reuse of K locations in a knowledge store
|Jul 20, 2005
|Aug 26, 2008
|Unisys Corporation
|Method for reducing the scope of the K node construction lock
|Sep 29, 2005
|Sep 9, 2008
|Unisys Corporation
|System and method for storing and accessing data in an interlocking trees datastore
|Oct 24, 2005
|Mar 3, 2009
|Unisys Corporation
|Accessing data in an interlocking trees data structure using an application programming interface
|Jul 5, 2005
|Mar 24, 2009
|International Business Machines Corporation
|System and method for selecting parameters for data mining modeling algorithms in data mining applications
|Mar 31, 2004
|May 19, 2009
|Google Inc.
|Query rewriting with entity detection
|Jun 29, 2004
|Sep 22, 2009
|Unisys Corporation
|Functional operations for accessing and/or building interlocking trees datastores to enable their use with applications software
|May 3, 2006
|Sep 29, 2009
|Chung Hua University
|Method of implementing B++ tree search on a parallel using virtual tree structure
|May 16, 2006
|Mar 9, 2010
|Unisys Corporation
|Method for processing a particle using a sensor structure
|Oct 24, 2005
|Mar 9, 2010
|Unisys Corporation
|Utilities for deriving values and information from within an interlocking trees data store
|Mar 24, 2006
|Mar 30, 2010
|Unisys Corporation
|Optimizing the size of an interlocking tree datastore structure for KStore
|Oct 27, 2004
|May 11, 2010
|Unisys Corporation
|Storing the repository origin of data inputs within a knowledge store
|Mar 20, 2006
|Jun 8, 2010
|Unisys Corporation
|Method for processing sensor data within a particle stream by a KStore
|May 26, 2005
|Jun 8, 2010
|International Business Machines Corporation
|Performance data for query optimization of database partitions
|Mar 18, 2005
|Aug 31, 2010
|Unisys Corporation
|System and method for storing and accessing data in an interlocking trees datastore
|Mar 31, 2004
|Nov 23, 2010
|Google Inc.
|Methods and systems for efficient query rewriting
|Oct 28, 2004
|Mar 15, 2011
|Unisys Corporation
|Facilitated use of column and field data for field record universe in a knowledge store
|Mar 31, 2004
|Aug 9, 2011
|Google Inc.
|Query rewriting with entity detection
|Apr 8, 2009
|Feb 7, 2012
|Google Inc.
|Query rewriting with entity detection
|Apr 4, 2006
|Aug 7, 2012
|Unisys Corporation
|Method for determining a most probable K location
|Jul 14, 2005
|Feb 26, 2013
|International Business Machines Corporation
|Method and apparatus for dynamically associating different query execution strategies with selective portions of a database table
|Dec 21, 2010
|Apr 16, 2013
|Fujitsu Limited
|Search device and search method
|Feb 6, 2012
|May 28, 2013
|Google Inc.
|Query rewriting with entity detection
|Mar 20, 2006
|Aug 20, 2013
|Unisys Corporation
|Method for processing K node count fields using an intensity variable
|Jul 14, 2011
|Aug 27, 2013
|Google Inc.
|Query rewriting with entity detection
|Nov 22, 2010
|Jan 14, 2014
|Google Inc.
|Methods and systems for efficient query rewriting
|Dec 23, 2002
|May 13, 2014
|Janssen Pharmaceutica, N.V.
|Data mining of SNP databases for the selection of intragenic SNPs
|May 24, 2013
|Aug 12, 2014
|Google Inc.
|Query rewriting with entity detection
|Aug 26, 2013
|Jun 2, 2015
|Google Inc.
|Query rewriting with entity detection
|Jan 24, 2013
|Jun 23, 2015
|International Business Machines Corporation
|Dynamically associating different query execution strategies with selective portions of a database table
|Jan 13, 2014
|Oct 20, 2015
|Google Inc.
|Efficient query rewriting
|Dec 23, 2002
|Oct 9, 2003
|Jan Aerts
|Data mining of SNP databases for the selection of intragenic SNPs
|Mar 1, 2005
|Jul 28, 2005
|Fujitsu Limited
|Information search system, information search method, information search apparatus, and recording medium to which information search program, is recorded and which can be read by computer
|Mar 31, 2004
|Oct 6, 2005
|Karl Pfleger
|Query rewriting with entity detection
|Mar 31, 2004
|Oct 6, 2005
|Hong Zhou
|Query rewriting with entity detection
|Sep 29, 2005
|Apr 6, 2006
|Mazzagatti Jane C
|System and method for storing and accessing data in an interlocking trees datastore
|Dec 16, 2004
|Jun 1, 2006
|Mazzagatti Jane C
|Method and apparatus for interface for graphic display of data from a KStore
|May 26, 2005
|Nov 30, 2006
|Inernational Business Machines Corporation
|Performance data for query optimization of database partitions
|Jun 8, 2006
|Dec 14, 2006
|Ryutaro Futami
|Optical receiver having bias circuit for avalanche photodiode with wide dynamic range
|Jul 5, 2005
|Jan 11, 2007
|International Business Machines Corporation
|System and method for selecting parameters for data mining modeling algorithms in data mining applications
|Jul 14, 2005
|Jan 18, 2007
|International Business Machines Corporation
|Method and apparatus for dynamically associating different query execution strategies with selective portions of a database table
|Jul 28, 2005
|Feb 1, 2007
|International Business Machines Corporation
|Method and apparatus for eliminating partitions of a database table from a join query using implicit limitations on a partition key value
|Oct 24, 2005
|Feb 15, 2007
|Mazzagatti Jane C
|API to KStore interlocking trees datastore
|Jan 10, 2007
|Jun 21, 2007
|Mazzagatti Jane C
|Saving and restoring an interlocking trees datastore
|Oct 24, 2005
|Jul 12, 2007
|Mazzagatti Jane C
|Updating information in an interlocking trees datastore
|May 3, 2006
|Sep 13, 2007
|Chung Hua University
|Method of implementing B++ tree search on parallel using virtual tree structure
|Mar 10, 2006
|Sep 13, 2007
|Mazzagatti Jane C
|Method for processing an input particle stream for creating upper levels of KStore
|Mar 20, 2006
|Sep 20, 2007
|Mazzagatti Jane C
|Method for processing K node count fields using an intensity variable
|Mar 20, 2006
|Sep 20, 2007
|Mazzagatti Jane C
|Method for processing an input particle stream for creating lower levels of a KStore
|Mar 20, 2006
|Sep 20, 2007
|Mazzagatti Jane C
|Method for processing sensor data within a particle stream by a KStore
|Apr 4, 2006
|Oct 4, 2007
|Mazzagatti Jane C
|Method for determining a most probable K location
|Oct 29, 2007
|Mar 13, 2008
|Mazzagatti Jane C
|Saving and restoring an interlocking trees datastore
|Mar 20, 2006
|Nov 6, 2008
|Jane Campbell Mazzagatti
|Method for processing counts when an end node is encountered
|Apr 8, 2009
|Aug 13, 2009
|Google Inc.
|Query rewriting with entity detection
|Dec 21, 2010
|Apr 21, 2011
|Fujitsu Limited
|Search device and search method
|U.S. Classification
|1/1, 707/999.006, 707/999.101
|International Classification
|Cooperative Classification
|European Classification
|Sep 3, 2002
Owner name: PARACEL, INC., CALIFORNIA
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:GIBSON, MICHAEL A.;MESSENGER, RICHARD J.;RIEFFEL, MARC A.;AND OTHERS;REEL/FRAME:013254/0163
Effective date: 20020813
|Mar 19, 2008
Owner name: CELERA, AN APPLERA CORPORATION BUSINESS, CALIFORNI
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:PARACEL, INC.;REEL/FRAME:020666/0558
Effective date: 20080311
Owner name: STRIKING DEVELOPMENT, INC., MICHIGAN
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:CELERA, AND APPLERA CORPORATION BUSINESS;REEL/FRAME:020666/0564
Effective date: 20080311
|Feb 23, 2009
|Maintenance fee reminder mailed
|Aug 16, 2009
|Lapse for failure to pay maintenance fees
|Oct 6, 2009
|Expired due to failure to pay maintenance fee
Effective date: 20090816


text:
10kts is definitely good Platu weather, but for Nataya (Rolf Heemskerk) to build on their lead from the first day, first they had to find the correct windward mark… 'The left was favoured for the beat,' said Heemskerk, 'but there were two windward marks – one black, the other black with a white stripe. We didn't see our mark against the light, and were happily sailed on towards the further one, with about two thirds of the fleet 'following-the-leader.' The boats that had gone right, early, were behind, and saw the mark against the land. They tacked on the correct layline, and all of a sudden the back portion of the fleet was in the lead.' That shook up the order a little, with Shaun Toh's SMU crew on Magic Dragon stepping up to enjoy a win, and Chris Weiguo's Naiad taking second place.
Newcomer to the Platu class, Simon Piff (One Two Two) scored 12,8,11 in today's three races, but declared himself delighted to be 'a little less last. But I wasn't expecting to be playing dodgem cars on the race track – the mark roundings were all incredibly congested. Yes, we are having fun!' Chris Way's Australian 'Easy Tiger' team on The Ferret, which includes Tom Spithill, made good today to take over the series lead.
Once again Sweet Chariot, John Higham's Sea Cart 26, left everyone else in their wake off the start line, and scored 2, 1 for the day. Next at the top mark in the first race was Andrew Stransky (Fantasia), but they missed the pin and had to tack in foul tide to make the mark. 15m cruising catamarans do not turn on a sixpence, and Fantasia got caught in irons and had to watch all the smaller multis come from behind and sail straight across her bows. The other Big Cat in the division, Khun Nim's Crowther 42, Sonic, scored an unexpected win in the first race of the day.
The three Shaw 650s look to have the Sportsboats class stitched up only halfway through the regatta. Crime Scene scored 1,1 today, Porn Star came in 2,2 and Hello Kitty followed on 3,3. Scott Duncanson's Phuket 8, Quantum, is out of the picture after her capsize and rescue yesterday, but was floated and then lifted out of the water today. 'At least we know that a Phuket 8 still floats when completely full of water,' said Duncanson. 'She's in the yard behind OMYC now. We've removed all the fish, frogs and seaweed, and cleaned her down. She'll be back in the water very soon – but not this week.'
Halfway through the regatta, and the racing is on schedule. The weather forecast indicates continuing unsettled weather – with wind – but probably with recurring small systems that play havoc with the RO's best laid plans, much like today.
Full Results: www.topofthegulfregatta.com
Short Results:
1 Karasu 3,5,1,1(10)
2= Walawala 6,4,5,2 (17)
2= Kukukerchu 2,1,6,8 (17)
1 Magic 1,2,1 (4)
2 El Coyote 3,1,2 (6)
3 Dynamite 2,4,3 (9)
1 Navy 1 1,1,2 (4)
2 Hi Jinks 3,4,1 (8)
3 Navy 2 2,3,3 (8)
Ocean Multihulls
1 Fantasia 2,1,5,2 (10)
2 Sweet Chariot 1,9,2,1 (13)
3 Free Wheeler 3,2,3,6 (14)
1 Crime Scene 1,1,1,1 (4)
3 Hello Kitty 3,7,3,3 (16)

subset: commoncrawl


text:
These are cheats, hints, unlockables for Army of Two: the 40th Day on Playstation 3 console.
Army of Two: The 40th Day Unlockable:
To unlock Big Heads and Infinite Ammo cheats, you must beat the game once on any difficulty. The cheat code will appear in Options Menu screen.
NOTE: when the cheats are activated, you won't be able to get any trophies or achievement.
Extra Costumes
After you beat the game once on any difficulty, you'll unlock several costumes. Here are the list of costumes that you can unlock:
- Civilian costume
- End costume
- Mall costume
- Medium Armor costume
- Old school costume
Extra Weapons
You must to have a save file from the original Army of Two to unlock the following weapons (open the customization menu to select the weapon):
- AS-KR1 (cost $300,000)
- SB-Z (cost $450,000)
Complete each requirement to receive the Trophies.
|How to Unlock
|Not What I Thought It Was (Bronze)
|Complete Chapter 1 on any difficulty level
|A Steep Descent (Bronze)
|Complete Chapter 2 on any difficulty level
|A Decent Animal (Bronze)
|Complete Chapter 3 on any difficulty level
|Emergency Room (Bronze)
|Complete Chapter 4 on any difficulty level
|Gone Shopping (Bronze)
|Complete Chapter 5 on any difficulty level
|Meat Bag (Bronze)
|Use 15 enemies as human shields
|Chaaaaarge! (Bronze)
|Charge through 20 enemies
|Grenadier (Bronze)
|Kill 3 or more enemies with a single grenade
|Pistolier (Bronze)
|Kill 150 enemies with pistols
|Old Faithful (Bronze)
|Kill 400 enemies with assault rifles, submachine guns or shutguns
|One Shot, One Kill (Bronze)
|Kill 100 enemies with a sniper rifle
|Quick Draw (Bronze)
|Kill 25 enemies with a quickdraw from mock surrender
|Open Hand Slap! (Bronze)
|Kill 50 enemies with a melee or bayonet
|Not So Bad After All (Bronze)
|Tie up 15 enemy combatants instead of executing them
|Healer (Bronze)
|Heal your partner 10 times
|Co-Op Sniper (Bronze)
|Co-op snipe 5 enemies
|Attention Grabber (Bronze)
|Allow your partner to snipe 5 guys while in mock surrender
|In Synch (Bronze)
|Kill two enemies with simultaneous quick draws while in co-op mock surrender
|Pumpkin Patch (Bronze)
|Shoot 2 enemies in the head with a single bullet
|Total Fist Bump Destruction (Bronze)
|Finish the game as best friends
|Total Fist Bump Deflation (Bronze)
|Finish the game in a fractured friendship
|The Truth Is Right Here (Bronze)
|Listen to all of the radio broadcasts
|Loot and Pillage (Bronze)
|Collect $1,000,000
|Hate Monger (Bronze)
|Customize a primary weapon to high aggro
|The Optimist (Bronze)
|Make a positive coop morality choice
|The Pessimist (Bronze)
|Make a negative coop choice
|Fresh Meat (Bronze)
|Versus: Revive your partner and perform a partner reload during the same public match
|Fancy Meeting You Here (Bronze)
|Versus: Invite a friend before joining a lobby to play a public match
|Big Game Hunting (Bronze)
|Versus: Kill both members of a single partnership during a public match
|Job Seeker (Bronze)
|Versus: In public matches, kill a player with either the primary or secondary weapon from every weapon kit
|DIY PMC (Bronze)
|Versus: Create a custom facemask online (www.armyoftwo.com) and wear it in a public match
|Death Dealer (Bronze)
|Versus: Kill 10 players on a single map in a public match
|Power Couple (Bronze)
|Versus: Earn the highest partnership score in a Co-op Deathmatch, Control or Warzone public match
|All Guns Blazing (Bronze)
|Versus: Kill a player with every weapon, including special weapons, in public matches
|Survivor? (Silver)
|Complete the game on any difficulty level
|Softcore (Silver)
|Complete half the game on hardest difficulty
|Unbreakable (Silver)
|Survive an entire level without needing to be revived on normal difficulty or above
|Full Arsenal (Silver)
|Collect all weapons and weapon parts
|Touch Not A Cat But A Glove (Silver)
|Shoot all Maneki Neko cats in the game
|Humanist (Silver)
|Save every hostage
|Future Visions (Silver)
|Unlock all potential futures
|Bound For Life (Silver)
|Versus: In a public match, survive an entire Extraction map without suffering a single death on your team
|King Of The Hill (Silver)
|Versus: Win a public match on every map in Co-op Deathmatch, Control and Warzone
|Survival Of The Fittest (Silver)
|Versus: Complete all 16 rounds of an Extraction game in a public match
|Hardcore (Gold)
|Complete the game on the hardest difficulty
|The Beast (Gold)
|Kill 6,666 people in Campaign
|Better Than Gold (Platinum)
|Earn all other trophies
|Rock, Paper, Scissors (Bronze)
|Beat your partner at rock, paper, scissors 3 times in a row
|Scavenger (Bronze)
|Build a gun using 3 homebrew parts
|Purist (Bronze)
|Make only positive choices
|Heartless (Bronze)
|Make only negative choices
These post contain Army of Two : The 40th Day cheats, hints, unlockable for Playstation 3 platform. Feel free to drop a comment if you have another cheats
Platform: Playstation 3
Tags: Army of Two, Army of Two: The 40th Day


text:
Select Committee on GRAS Substances (SCOGS) Opinion: Thiamine mononitrate
The GRAS Substances (SCOGS) Database allows access to opinions and conclusions from 115 SCOGS reports published between 1972-1980 on the safety of over 370 Generally Recognized As Safe (GRAS) food substances. The GRAS ingredient reviews were conducted by the Select Committee in response to a 1969 White House directive by President Richard M. Nixon.
Thiamine mononitrate
- SCOGS-Report Number: 109*
- Type Of Conclusion: 1
- ID Code: 532-43-4
- Year: 1978
- 21 CFR Section: 184.1878
SCOGS Opinion:
Thiamin† (thiamine) salts have been administered to man for months in daily doses up to 1 g or more without reported adverse effects, except hundred times the estimated intake of thiamin hydrochloride and thiamin monotrinate added to foods. Most cases of sensitivity were induced by previous topical or parenteral exposure to thiamin.
Similarly, mice and rats fed daily for three generations with several hundred times their normal requirements of thiamin showed no adverse effects.
Absorption of orally administered thiamin is regulated by a transport mechanism which offers an effective protection against overdosage. Excess thiamin in the tissues is rapidly excreted in the urine.
In view of the above considerations, the Select Committee concludes that:
There is no evidence in the available information on thiamin hydrochloride or thiamin mononitrate that demonstrates, or suggests reasonable grounds to suspect, a hazard to the public when it is used at levels that are now current or that might reasonably be expected in the future.
† This spelling has been recommended by the International Union of Nutrition Sciences and by the American Institute of Nutrition.
*Complete reports containing details of the safety studies that formed the basis of the opinions and conclusions and are available from the National Technical Information Service (NTIS), 5285 Port Royal Road, Springfield, VA 22161 (703) 605-6000.


text:
More than 25 percent of consumers in the United States own and use logoed drinkware every single day. This data alone makes these products a powerful mechanism to promote your event, raise your brand awareness, and lift the ceiling on revenue earning potential for years to come. At ePromos, we believe in offering glassware and other products that stand up to repeated use, are simple to clean, and won't dull over time, giving your promotional efforts the longevity they deserve. Whether you're looking for shatterproof plastic or printed pint glasses, our selection offers a robust catalog that won't send you away in search of better options.
A resuable alternative to plastic bottles, this promotional water bottle comes with a screw lid and snap cap.
Before your hit the trails remember to grab your promotional sports bottle.
An imprinted sports bottle made of lightweight aluminum that features a carabiner with a nylon strap for convenient carrying.
This promotional water bottle is great for sporting events, corporate picnics and fundraiser walks.


text:
BANANA KONG For PC Online Free Download And Install
BANANA KONG For PC Online Free Download And Install-Once again we are going to share a awesome apps/game- BANANA KONG. If you want to play/use online BANANA KONG on your PC/Computer then get ready for this. BANANA KONG is awsome apps/game.
Lots of android users are enjoying by using this apps/game on their android smartphone. If you have not android smartphone, then don't worry . We are here to help you to play/use online BANANA KONG on PC/Laptop on any OS like as Windows Xp/7/8/10 And MAC.
Here we will explain all the topic related to DR. BANANA KONG for PC:-
Download BANANA KONG On PC
BANANA KONG Para PC
BANANA KONG Online
BANANA KONG On PC
BANANA KONG For PC
BANANA KONG For MAC
Free Download BANANA KONG
BANANA KONG APK Download
We are going to cover all of these topics. Just read all of this post and get ready to Play/use this apps/game on your computer.
BANANA KONG For PC Online Download And Install
Its very easy, just keep reading carefully then you will understand whole method. Just read how to Play/use BANANA KONG On PC Online:-
Step 1- First it will be needed a best Android Emulator. We can not use BANANA KONG Online on PC without Android Emulator.
Step 2– So we will suggest to use Bluestacks, which is a best Android Emulator. Its very easy to use and handle.
Step 3- Now just download Bluestacks and install it on your Computer/PC. If any problem then just comment your problem here.
Step 4- After that start Bluestacks and just go on search option. Search there- BANANA KONG.
Step 5- Now just Download and install BANANA KONG on Bluestacks.
Step 6- Just double click on BANANA KONG icon and it will be start. Now play/use onlinje BANANA KONG on PC.
Its done BANANA KONG For PC Online.
BANANA KONG For PC Online Features
While you dash through the jungle you'll be able to outrun your friends! Thanks to full Game Services integration you can see your friends best distance right in the game. Compare your high scores and unlock achievements while improving your playing style.
Its completed. Now you can use this awesome apps/game on your computer/pc. Just play/use Online BANANA KONG On PC. If you have any queries related to BANANA KONG For PC then just give a comment here, we will try to solve all of your problems. So enjoy BANANA KONG For PC Online.


text:
The bank said a slowdown in the UK's mortgage market was over its worst, and had been through "the trough".
"While the outlook in the first quarter was uncertain... people are much more confident about the second half," said chief executive Steven Crawshaw.
Underlying pre-tax profit for the six months to 30 June rose to £150m ($268m) from £139.4m at the same time in 2004.
Total underlying net income remained flat at £281m, but underlying costs fell 6% thanks to a cost-cutting programme introduced by Mr Crawshaw.
However, by the close of trade on the London market Bradford & Bingley's shares were down 3.55% to 325.75 pence.
Gross new home loans at the bank fell 40% in the first half of 2005 - from a record £4.1bn in the same period last year - but lending profit rose 8% to £120m as fewer existing mortgage holders moved away from its loans.
"The main reason for lower-than-expected income was that loans have only grown 1.4 % since the end of the year, and slowing volumes is an issue flagged by management," Merrill Lynch analyst James Invine wrote in a note.


text:
Augustana CORE: Careers, Opportunities, Research and Exploration
Finalized May 2017
Augustana Careers, Opportunities, Research, and Exploration (CORE) is designed to build a more active and robust community of alumni, parents, and employers; lead students through vocational discernment, skill development for employment and appropriate internships; and integrate a student's professional development with academic advising and academic enrichment opportunities such as international and off-campus programs, undergraduate research and service learning. CORE's comprehensive approach will better position Augustana graduates to pursue meaningful careers that honor their aspirations and investment in their education.
Offices and functions in Augustana CORE include:
Careers & Professional Development
International and Off-Campus Study


text:
Sort By
Terminator 3: Rise of the Machines(2003)
After Skynet fails to kill Sarah Connor before her son is born and to kill John himself as a child, it sends back another Terminator, the T-X, in an attempt to wipe out as many Resistance officers as possible. This includes John's future wife, but not John himself as his whereabouts are unknown to S...
Terminator 2: Judgment Day(1991)
The terminator (Anorld Schwarzenegger) has returned and this time he has a new mission and that is to protect the leader of the human-led resistance against the machines, John Connor (Edward Furlong) son of Sarah Connor (Linda Hamilton) who was first targeted. The terminator was sent by John Connor...
The Terminator(1984)
In the year 2029, super computers dominate the world, with only one intention, the extermination of the human race. They send an indestructible human-like cyborg, called a terminator, back in time to kill Sarah Connor whose unborn child will eventually become mankind
Terminal Velocity(1994)
Ditch Brodie is a maverick skydiving instructor. One day, a beautiful girl comes in, wanting to take her first jump. Up in the air, Ditch takes his eyes off her momentarily, then looks back to find out that she has fallen out, dying on impact. Ditch is suspicious that all is not as it seems, because...
Terminal Island(1973)
It's every man and woman for himself on an island where convicted murderers are dumped, rather than kept in prison.
Terminal City Ricochet(1990)
Welcome to Terminal City, a decaying world where the citizens wallow amidst a mind-boggling profusion of discarded consumer goods; a ruthless world where television is exploited to its fullest to sell yet more needless junk to eager consumers; a bewildering land where the unreal is real and the real...
Tequila Sunrise(1988)
Dale "Mac" McKussic (Mel Gibson) is a former drug dealer trying to go straight. His close friend Nick Frescia (Kurt Russell) is a detective lieutenant who, in spite of their friendship, is duty-bound to bring Mac to justice if he is selling drugs again, as Agent Hal Maguire (J. T. Walsh) of the Drug...
An American writer in Rome is stalked by a serial killer bent on harassing him while killing all people associated with his work on his latest book.
An American writer in Rome is stalked by a serial killer bent on harassing him while killing all people associated with his work on his latest book.
The Ten Commandments(1956)
The Egyptian Pharaoh, Ramesses I has ordered the death of all firstborn Hebrew males, but a Hebrew woman sets her infant son adrift on the Nile in order to save him. The infant is rescued from the Nile by an Egyptian princess who decides to adopt the boy even though her servant recognizes that the c...


text:
If account is locked or deactivated, or you forgot your user ID, contact your Technology Manager administrator.
Users: Update Password/Profile
Admins: Manage Applications/Users
Missing/Defective Document Request Report Updated by Lender Request
In response to lender requests, the Missing/Defective Document Request report now maintains information for 60 days on your document submissions (shown by loan number). Tip: Documents that Fannie Mae requested will always be on top, followed by any documents you submitted without a request. If a Document Due Date is displayed and the Document Received Date is blank, the requested document must be provided to Fannie Mae by the due date.
The updated matrix features easier navigation, a simpler look and feel, and streamlined documentation requirements for some data attributes and SFCs.
The Loan Quality Center (LQC) FT Portal is an electronic file submission platform through which lenders submit loan files that have been selected for a post-purchase file review. The LQC FT Portal replaces paper and/or CD/DVD loan file submissions for lenders with low to medium file request volumes (higher-volume lenders may invest in Lender Direct (B2B) integration). Files uploaded through the FT Portal are visible in QAS within 2 business days or less.
Have a question? Access the page below to contact the Technology Support Center for help.