Michael G. Walker
Research Subjects
Michael G. Walker has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
Wayne Volkmuth
2 shared publicationsDavid Hodgson
Incyte Pharmaceuticals, Palo Alto, California 94304 USA; 2Department of Medicine, Stanford University, Stanford, California 94305 USA
1 shared publicationEinat Sprinzak
Incyte Pharmaceuticals, Palo Alto, California 94304 USA; 2Department of Medicine, Stanford University, Stanford, California 94305 USA
1 shared publication- Eldar Giladi
Incyte Genomics, 3160 Porter Drive, Palo Alto, CA 94304, USA; US
1 shared publication James Z. Wang
1 shared publicationT M Klingler
1 shared publication
Latest Publications
- Open Access
- 1 June 2002
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 18 (6) , 873-877
SST: an algorithm for finding near-exact sequence matches in time proportional to the logarithm of the database size
Motivation: Searches for near exact sequence matches are performed frequently in large-scale sequencing projects and in comparative genomics. The time and cost of performing these large-scale sequence-similarity searches is prohibitive using even the fastest of the extant algorithms. Faster algorithms are desired. Results: We have developed an algorithm, called SST (Sequence Search Tree), that searches a database of DNA sequences for near-exact matches, in time proportional to the logarithm of the database size n. In SST, we partition each sequence into fragments of fixed length called ‘windows’ using multiple offsets. Each window is mapped into a vector of dimension 4k which contains the frequency of occurrence of its component k-tuples, with k a parameter typically in the range 4–6. Then we create a tree-structured index of the windows in vector space, with tree-structured vector quantization (TSVQ). We identify the nearest neighbors of a query sequence by partitioning the query into windows and searching the tree-structured index for nearest-neighbor windows in the database. When the tree is balanced this yields an O(logn) complexity for the search. This complexity was observed in our computations. SST is most effective for applications in which the target sequences show a high degree of similarity to the query sequence, such as assembling shotgun sequences or matching ESTs to genomic sequence. The algorithm is also an effective filtration method. Specifically, it can be used as a preprocessing step for other search methods to reduce the complexity of searching one large database against another. For the problem of identifying overlapping fragments in the assembly of 120 000 fragments from a 1.5 megabase genomic sequence, SST is 15 times faster than BLAST when we consider both building and searching the tree. For searching alone (i.e. after building the tree index), SST 27 times faster than BLAST. Availability: Request from the authors. Contact: egiladi@incyte.com mwalker@incyte.com
- 1 June 2002
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 18 (6) , 873-877
Open AccessSST: an algorithm for finding near-exact sequence matches in time proportional to the logarithm of the database size
Motivation: Searches for near exact sequence matches are performed frequently in large-scale sequencing projects and in comparative genomics. The time and cost of performing these large-scale sequence-similarity searches is prohibitive using even the fastest of the extant algorithms. Faster algorithms are desired. Results: We have developed an algorithm, called SST (Sequence Search Tree), that searches a database of DNA sequences for near-exact matches, in time proportional to the logarithm of the database size n. In SST, we partition each sequence into fragments of fixed length called ‘windows’ using multiple offsets. Each window is mapped into a vector of dimension 4k which contains the frequency of occurrence of its component k-tuples, with k a parameter typically in the range 4–6. Then we create a tree-structured index of the windows in vector space, with tree-structured vector quantization (TSVQ). We identify the nearest neighbors of a query sequence by partitioning the query into windows and searching the tree-structured index for nearest-neighbor windows in the database. When the tree is balanced this yields an O(logn) complexity for the search. This complexity was observed in our computations. SST is most effective for applications in which the target sequences show a high degree of similarity to the query sequence, such as assembling shotgun sequences or matching ESTs to genomic sequence. The algorithm is also an effective filtration method. Specifically, it can be used as a preprocessing step for other search methods to reduce the complexity of searching one large database against another. For the problem of identifying overlapping fragments in the assembly of 120 000 fragments from a 1.5 megabase genomic sequence, SST is 15 times faster than BLAST when we consider both building and searching the tree. For searching alone (i.e. after building the tree index), SST 27 times faster than BLAST. Availability: Request from the authors. Contact: egiladi@incyte.com mwalker@incyte.com
- 1 July 2001
- Published by Bentham Science Publishers Ltd. in Mini-Reviews in Medicinal Chemistry
- Vol. 1 (2) , 197-205
Pharmaceutical Target Identification by Gene Expression Analysis
The majority of newly-identified genes in the human genome show no significant sequence similarity to genes whose function is known, so they are not easily recognized as potential drug targets. Expression analysis is an alternative method to suggest possible functions of genes. We review statistical methods for gene expression analysis to identify potential pharmaceutical targets. Specifically, we illustrate the analysis of differential gene expression (using discriminant analysis, t-tests, and analysis of variance) and co-expression (using correlation, clustering, and chi-square). We present an example of the use of expression analysis to identify co-expressed cardiomyopathy-associated genes.
- 1 July 2001
- Published by Bentham Science Publishers Ltd. in Mini-Reviews in Medicinal Chemistry
- Vol. 1 (2) , 197-205
Pharmaceutical Target Identification by Gene Expression Analysis
The majority of newly-identified genes in the human genome show no significant sequence similarity to genes whose function is known, so they are not easily recognized as potential drug targets. Expression analysis is an alternative method to suggest possible functions of genes. We review statistical methods for gene expression analysis to identify potential pharmaceutical targets. Specifically, we illustrate the analysis of differential gene expression (using discriminant analysis, t-tests, and analysis of variance) and co-expression (using correlation, clustering, and chi-square). We present an example of the use of expression analysis to identify co-expressed cardiomyopathy-associated genes.
- Open Access
- 1 December 1999
- Published by Cold Spring Harbor Laboratory in Genome Research
- Vol. 9 (12) , 1198-1203
Prediction of Gene Function by Genome-Scale Expression Analysis: Prostate Cancer-Associated Genes
We wish to identify genes associated with disease. To do so, we look for novel genes whose expression patterns mimic those of known disease-associated genes, using a method we call Guilt-by-Association (GBA), on the basis of a combinatoric measure of association. Using GBA, we have examined the expression of 40,000 human genes in 522 cDNA libraries, and have discovered several hundred previously unidentified genes associated with cancer, inflammation, steroid-synthesis, insulin-synthesis, neurotransmitter processing, matrix remodeling, and other disease processes. The majority of the genes thus discovered show no sequence similarity to known genes, and thus could not have been identified by homology searches. We present here an example of the discovery of eight genes associated with prostate cancer. Of the 40,000 most-abundant human genes, these 8 are the most closely linked to the known diagnostic genes, and thus are prime targets for pharmaceutical research.[The sequence data described in this paper have been submitted to the GenBank data library under accession nos.AF109298–AF109303.]
- 1 December 1999
- Published by Cold Spring Harbor Laboratory in Genome Research
- Vol. 9 (12) , 1198-1203
Open AccessPrediction of Gene Function by Genome-Scale Expression Analysis: Prostate Cancer-Associated Genes
We wish to identify genes associated with disease. To do so, we look for novel genes whose expression patterns mimic those of known disease-associated genes, using a method we call Guilt-by-Association (GBA), on the basis of a combinatoric measure of association. Using GBA, we have examined the expression of 40,000 human genes in 522 cDNA libraries, and have discovered several hundred previously unidentified genes associated with cancer, inflammation, steroid-synthesis, insulin-synthesis, neurotransmitter processing, matrix remodeling, and other disease processes. The majority of the genes thus discovered show no sequence similarity to known genes, and thus could not have been identified by homology searches. We present here an example of the discovery of eight genes associated with prostate cancer. Of the 40,000 most-abundant human genes, these 8 are the most closely linked to the known diagnostic genes, and thus are prime targets for pharmaceutical research.[The sequence data described in this paper have been submitted to the GenBank data library under accession nos.AF109298–AF109303.]
- 1 January 1999
- p. 282-6
Pharmaceutical target discovery using Guilt-by-Association: schizophrenia and Parkinson's disease genes.
We wish to identify genes associated with disease. To do so, we look for novel genes whose expression patterns mimic those of known disease-associated genes, a method we call Guilt-by-Association (GBA). GBA uses a combinatoric measure of association that provides superior results to those from correlation measures used in previous expression analyses. Using GBA, we have examined the expression of 40,000 human genes in 522 cDNA libraries, and have identified several hundred genes associated with known cancer, inflammation, steroid-synthesis, insulin-synthesis, neurotransmitter processing, matrix remodeling and other disease genes. The majority of the genes thus discovered show no significant sequence similarity to known genes, and thus could not have been identified by homology searches. We present here an example of the discovery of five genes associated with schizophrenia and Parkinson's disease. Of the 40,000 most-abundant human genes, these five genes are the most closely linked to the known disease genes, and thus are prime targets for pharmaceutical intervention.
- 1 January 1999
- p. 282-6
Pharmaceutical target discovery using Guilt-by-Association: schizophrenia and Parkinson's disease genes.
We wish to identify genes associated with disease. To do so, we look for novel genes whose expression patterns mimic those of known disease-associated genes, a method we call Guilt-by-Association (GBA). GBA uses a combinatoric measure of association that provides superior results to those from correlation measures used in previous expression analyses. Using GBA, we have examined the expression of 40,000 human genes in 522 cDNA libraries, and have identified several hundred genes associated with known cancer, inflammation, steroid-synthesis, insulin-synthesis, neurotransmitter processing, matrix remodeling and other disease genes. The majority of the genes thus discovered show no significant sequence similarity to known genes, and thus could not have been identified by homology searches. We present here an example of the discovery of five genes associated with schizophrenia and Parkinson's disease. Of the 40,000 most-abundant human genes, these five genes are the most closely linked to the known disease genes, and thus are prime targets for pharmaceutical intervention.