Methods for establishing a pathways database and performing pathway searches

• US 7,058,650 B2
• Filed: 02/20/2002
• Issued: 06/06/2006
• Est. Priority Date: 02/20/2001
• Status: Expired due to Fees

• Current Assignee: Christopher Piercy, John Tillinghast, Yonghong Yang
• Original Assignee: Christopher Piercy, John Tillinghast, Yonghong Yang
• Inventors: Yang, Yonghong, Piercy, Christopher, Tillinghast, John
• Primary Examiner(s): Zeman, Mary K.
• Application Number:
  US10/081,904
• Publication Number:
  US 20030100996A1
• Time in Patent Office: 1,567 Days
• Field of Search: 707/102, 707/1, 702 19- 20, 703/11, 435/6, 435/7.1, 530/300, 530/350
• US Class Current: 707/700
• CPC Class Codes: G16B 5/00 ICT specially adapted for modelling or simulations in systems biology, e.g. gene-regulatory networks, protein interaction networks or metabolic networks
• CPC Class Codes: G16B 50/00 ICT programming tools or database systems specially adapted for bioinformatics
• CPC Class Codes: G16B 50/20 Heterogeneous data integration
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

The invention provides a computerized storage and retrieval system for storing biological information organized as a protein pathways database and methods for performing pathway searches on nodes (proteins or other molecules), modes (interactions), and nodes-and-modes. The protein pathways database is a relational database that integrates protein sequence, genomic sequence, gene-expression, protein interactions, protein-protein association and pathway data and can be searched using a query pathway to predict homologous or orthologous nodes, modes, and pathways.

Claims

1. A computerized storage and retrieval system of biological information comprising:

a means for entering data;

a means for displaying the data;

a programmable central processing unit programmed to perform automated analysis using semi-linear pathway representation (SLIPR) to compare and predict pathways and their components and to establish a pathways database;

a means for storing data; and

a relational database containing annotated and curated pathways and information on the pathways and their components.

2. The system of claim 1, wherein the information pertaining to the pathways and their components and stored in a plurality of tables further comprises proteins, their sequences and attributes;

protein interactions;

protein-protein associations;

protein pathways;

mRNA, microarray, and protein expression data;

genes, their sequences and attributes;

descriptions of cells, tissues, and organs;

pathology reports;

patient histories and treatments.

3. The system of claim 1, wherein the central processing unit is further programmed to run an algorithm or a method for constrained clustering or an optimization algorithm for dynamic programming and one or more functions or standard methods selected from retrieve, input, edit, annotate, search, calculate similarities, align, compare, optimize using linear next-neighbor criteria or global minimization criteria, and predict homologous or orthologous pathways and their components and, wherein the method for constrained clustering is further selected from average linkage, single linkage, complete linkage, K-means, or self-organizing maps.

4. The system of claim 3, wherein the central processing unit runs the optimization algorithm for dynamic programming further comprising:

a) initializing an array, in which a two dimensional array M=M_ij with J rows and variant length for each row, the length for i-th row is n_i is set up and M_ji=0, where 1<

=i<

=n_J,

b) backfilling the array via backward recursion with the formula

$M_{\mathrm{ik}}=\underset{\underset{1\le <br><br>l\le <br><br>n_j}{j><br><br>i}}{\max }<br><br>\left\{w<br><br>\left(a_{\mathrm{ik}},a_{\mathrm{jl}}\right)+M_{\mathrm{jl}}<br><br>\mathrm{\theta <br><br>}<br><br>\left(w<br><br>\left(a_{\mathrm{ik}},a_{\mathrm{jl}}\right)\right)\right\}$ $\mathrm{for}<br><br><br><br>1\le <br><br>k\le <br><br>n_i,1\le <br><br>i\le <br><br>J$

where è

(.) is the step function defined as è

(v)={0, if v<

=0;

1, if v>

0} and w(.,.) is the scoring function between the two nodes, defined as

$w<br><br>\left(a_{\mathrm{ik}<br><br>},a_{\mathrm{jl}}\right)=\{\begin{array}{c}0,\mathrm{if}<br><br><br><br>i=j,a_{\mathrm{ik}}=a_{\mathrm{jl}},a_{\mathrm{ik}}=-D,\mathrm{or}<br><br><br><br>a_{\mathrm{jl}}=-D\\ \mathrm{where}<br><br><br><br>D><br><br>0,\mathrm{or}<br><br>\\ \mathrm{\theta <br><br>}<br><br>\left[c_{\mathrm{ik},\mathrm{jl}}-t_c\right]·<br><br>\left\{\mathrm{\alpha <br><br>}<br><br>\left(1-<br><br>s_{\mathrm{ik}}-s_{\mathrm{jl}}<br><br>\right)+\left(1-\mathrm{\alpha <br><br>}\right)<br><br>c_{\mathrm{ik},\mathrm{jl}}\right\}<br><br><br><br>\mathrm{otherwise};<br><br>\end{array}$

c) finding the best alignment to predict nodes of putative pathways PPW_j, 1<

=j<

=max n_i with the top n best scores.

5. The system of claim 3, wherein the central processing unit runs the constrained clustering algorithm further comprising:

a) assigning a distance between a protein in a query pathway and each protein in the database;

b) merging at each round the protein in the query pathway and the protein in the database with the closest distance into a cluster until user-set threshold is met; and

c) computing mean linkage between two clusters using

$d<br><br>\left(c_1,c_2\right)={\left\{\frac{1}{n_1+n_2}<br><br>\underset{i\in <br><br><br><br>c_1}{\sum <br><br>}<br><br><br><br>\underset{j\in <br><br><br><br>c_2}{\sum <br><br>}<br><br><br><br>d_{\tilde{u}}^{\mathrm{\rho <br><br>}}\right\}}^{1/\mathrm{\rho <br><br>}}$

where n₁ is the size of c₁ and n₂ is the size of c₂ and the distance between the two clusters is a weighted average of the distance between two proteins i and j and a function or similarity to query protein (s_i=S_iq(i), s_j=S_jq(j)) where q(i) is the query protein homologous to database protein i and protein-protein association (a_ij) and

d_ij=α

(1−

α

_ij)+(1−

α

)|s_i−

s_j|.

6. The system of claim 1, wherein the central processing unit is further programmed to perform one or more analyses selected from protein sequence analysis, protein interactions analysis, protein-protein association analysis, protein pathway analysis, gene expression analysis, pathway annotation analysis, pathway edit analysis, pathway expression analysis, tissue expression analysis, subtractive hybridization analysis, electronic northern analysis, and commonality analysis.

7. The system of claim 6, wherein protein interactions analysis between a query pathway and each pathway in the database produces a coefficient of similarity to interrelate each mode of the query pathway and a mode of the most closely related protein pathway.

8. The system of claim 1, which each pathway in the database further comprises at least two nodes connected by a mode.

9. The system of claim 8 wherein the central processing unit is further programmed to compare at least two pathways using scores calculated from sequence identity, motif or structural homologies that interrelate nodes and employing coefficients of similarity calculated or selected from gene expression data, a promoter similarity matrix, a protein-protein association matrix and a similarities among protein interactions matrix (SCIM matrix) that interrelate modes of the pathways.

10. The system of claim 1, wherein the central processing unit is further programmed to perform pairwise comparison of at least two pathways or their components selected from node-only, mode-only, and node-and-mode comparison and wherein the node-only comparison is further selected from protein only, non-protein only, and protein and non-protein nodes.

11. The system of claim 10, wherein node-and-mode comparison predicts new homologous or orthologous pathways by comparing node by using an optimization algorithm for dynamic programming or a constrained clustering algorithm or standard methods and modes by generating a SCIM matrix containing coefficients of similarity.

12. A process for analyzing or predicting novel homologous or orthologous pathways comprising:

a) submitting a query pathway and protein sequences to the system of claim 1;

b) organizing the pathway and sequences using SLIPR;

c) comparing each sequence of the query pathway with each sequence in the pathways database using an algorithm for constrained clustering or an optimization algorithm for dynamic programming and standard methods of protein comparison to calculate sequence identity scores;

d) using a SCIM matrix derived from protein interactions protein-protein association analysis to compare coefficients of similarity for each interaction of the query pathway and each interaction in a pathway in the pathways database;

e) calculating an overall-similarity score (OS-score) based on sequence identity scores and coefficients of similarity for each pathway; and

f) retrieving pathways meeting a user-specified threshold for OS-score, thereby analyzing or predicting novel homologous or orthologous pathways.

13. The process of claim 12, wherein the predicted orthologous pathway further comprises orthologous proteins with the highest sequence identity to the proteins in the query pathway and protein interactions inherited from the query pathway.