G - Physics – 06 – F
Patent
G - Physics
06
F
G06F 17/30 (2006.01)
Patent
CA 2395327
A method and system for generating and searching a tree-structured index of window vectors that represent database sequences comprise a window vector generation module, a tree-structured index generation module, a query sequence partitioning module, and a retrieval component. The window vector generation module partitions a database sequence into a plurality of overlapping windows. Each window has a fixed length W comprising a fixed number of nucleotides, and the offset among windows is determined by a parameter .DELTA.. The window vector generation module then maps each database sequence window into a window vector. The database sequence window vector indicates the frequency of appearance of each k-tuple in the corresponding database sequence window. The tree-structured index generation module then generates a tree-structured index using the database sequence window vectors. The query sequence partitioning module partitions a query sequence into a plurality of windows and maps each query sequence window into a query sequence window vector. Each query sequence window vector is then compared against the tree-structured index to locate the database sequences that are similar to the query sequence. The list database sequences that are similar to the sequence is then returned as the result of the search.
Selon l'invention, un procédé et un système pour générer et rechercher un index de vecteurs de fenêtres qui représentent les séquences d'une base de données comprennent un module de génération de vecteurs de fenêtres, un module de génération d'index structuré en forme d'arbre, un module de partition des séquences d'interrogation et un composant de récupération. Le module de génération de vecteurs de fenêtres partitionne une séquence de base de données en plusieurs fenêtres superposées. Chaque fenêtre possède une longueur fixe W comprenant un nombre fixe de nucléotides, et le décalage entre les fenêtres est déterminé par un paramètre .DELTA.. Le module de génération de vecteurs de fenêtres effectue ensuite le mappage de chaque fenêtre de séquences de base de données pour obtenir un vecteur de fenêtres. Le vecteur de fenêtres de séquences de bases de données indique la fréquence d'apparition de chaque multiple k dans la fenêtre correspondante de séquences de base de données. Le module de génération d'index des structures en arbre génère ensuite un index structuré en forme d'arbre en utilisant le vecteur de fenêtres de séquences de base de données. Le module de partition des séquences d'interrogation partitionne une séquence d'interrogation en plusieurs fenêtres et effectue le mappage de chaque fenêtre de séquences d'interrogation pour obtenir un vecteur de fenêtre de séquences d'interrogation. Chaque vecteur de fenêtres de séquences d'interrogation est ensuite comparé avec l'index structuré en forme d'arbre pour localiser les séquences de base de données similaires à la séquence d'interrogation. La séquence de base de données de la liste similaire à la séquence est ensuite retournée sous forme de résultat de recherche.
Giladi Eldar Y.
Walker Michael G.
Wang James Z.
Incyte Genomics Inc.
Sim & Mcburney
Stanford University
LandOfFree
Sequence database search with sequence search trees does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Sequence database search with sequence search trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sequence database search with sequence search trees will most certainly appreciate the feedback.
Profile ID: LFCA-PAI-O-1562739