Sequence database search with sequence search trees

In a computer having a processor and a storage device, the storage device storing a plurality of database sequences in computer-readable form, each database sequence representing a biological sequence of nucleotides, a computer-implemented process for selecting a database sequence in response to an input query sequence representing a biological sequence of nucleotides, the process comprising:

• generating a plurality of window vectors representing the content of the database sequences;
• generating a tree-structured index of the database sequences according to positions of the window vectors in a multidimensional space;
• and
• using the input query sequence to search the tree-structured index to identify database sequences similar to the query sequence.

A computer-implemented process for generating a tree-structured index representing database sequences, the process comprising:

• partitioning each database sequence into a plurality of overlapping windows;
• mapping each window into a window vector that represents the content of the window;
• and
• generating the tree-structured index for the overlapping windows according to positions of the window vectors in a multidimensional space.

In a computer-implemented system comprising a plurality of database sequences, a system for generating a tree-structure index that represents the database sequences, the system for generating a tree structure index comprising:

• a computer-readable medium for storing program instructions for execution by a processor;
• a window vector generating component, stored on the computer-readable medium and executable by the processor, for mapping each database sequence into a window vector, the window vector representing the content of the database sequence;
• and
• a tree-structure index generator, stored on the computer-readable medium and executable by the processor, for generating a tree-structure index of the window vectors in accordance with positions of the window vectors in a multidimensional space.

A computer-implemented system for selecting database sequences from a database comprising a plurality of sequences stored in electronic form, the system comprising:

• a computer processor for executing programmed instructions and for storing and retrieving data;
• an input device, coupled to the processor, for receiving a query sequence;
• a program memory, coupled to the processor, for storing program instructions for execution by the processor;
• a window vector generating component, stored in the computer readable medium and executable by the processor, for mapping each database sequence into a window vector, where the window vector represents the content of the database sequence;
• a tree-structure index generator, executable by the processor in accordance with program instructions in the program memory, for generating a tree-structure index that represents the database sequences, where the tree-structure index is generated in accordance with positions of the window vectors in a multi-dimensional space;
• a query sequence partitioning component, executable by the processor in accordance with program instructions in the program memory, for partitioning a query sequence into a plurality of windows;
• and
• a retrieval component, executable by the processor in accordance with program instructions in the program memory, for retrieving database sequences from the database that are similar to the query sequence.

A computer readable memory, for use with a processor and a plurality of database sequences, the memory storing a computer program executable by the processor for configuring and controlling the processor to generate a tree-structured index that represents the database sequences, by performing the steps of:

• partitioning each database sequence into a plurality of overlapping windows;
• for each window, generating a window vector representing the content of the window;
• and
• generating a tree-structured index of the window vectors according to positions of the window vectors in a multidimensional space.

A computer readable memory, for use in a computer system comprising a processor and a database storing a plurality of database sequences in computer-readable form, and for selecting database sequences from the database in response to a query sequence, the computer readable memory storing:

• a window vector generating component, stored in the computer readable medium and executable by the processor, for mapping each database sequence into a window vector, where the window vector represents the content of the database sequence;
• a tree-structured index generator, executable by the processor in accordance with program instructions in the memory, for generating a tree-structured index that represents the database sequences, where the tree-structure index is generated in accordance with positions of the window vectors in a multidimensional space;
• a query sequence partitioning component, executable by the processor in accordance with program instructions in the memory, for partitioning a query sequence into a plurality of windows;
• and
• a retrieval component, executable by the processor in accordance with program instructions in the memory, for retrieving database sequences from the database that are similar to the query sequence.