Walter L. Ruzzo Professor, Computer Science & Engineering Adjunct Professor, Genome Sciences Joint Member, Fred Hutchinson Cancer Research Center

Currently, his principal research project involves the construction and programming of a vaguely parallel computer, consisting of 32 steam-powered Turing machines installed in the basement of Sieg Hall. Of particular interest is the use of triple-expansion bypass valves, coupled to individual governors on each engine, to achieve write-synchronization of the machines. Graduate students have played an important role in the construction and operation of the engine, particularly in stoking the boilers, and advanced undergraduates are occasionally allowed to polish the brass gauges.

Originally intended as a general computing engine, restrictions imposed by the Pollution Control and Noise Abatement Boards require that only algorithms running in polynomial time may be used. The project recently suffered another setback when one of Professor Ruzzo's graduate students slipped on a mouldering stack of ungraded homework exercises and fell under the write head of one of the machines. Now permanently embossed with a series of 1's and 0's, the student is suing to have the machine dismantled.

When not blowing off steam, he also pursues research in computational biology as part of the CSE department's Computational and Synthetic Biology Group , as well as participating in graduate training through the interdisciplinary graduate program in Computational Molecular Biology and, of course, undergraduate and graduate education in Computer Science & Engineering.

Publications:

For an up-to-date publications list, see my new home page, or search via Pubmed and/or DBLP.

The list below, while no longer maintained, contains links to supplementary information in some cases.

Older Publications:

Computational Biology

• Cao, Yao, Sarkar, Lawrence, Sanchez, Parker, MacQuarrie, Davison, Morgan, Ruzzo, Gentleman and Tapscott. Genome-wide MyoD binding in skeletal muscle cells: a potential for broad cellular reprogramming. Developmental Cell. 2010 Apr 20; 18(4):662-74. PMID: 20412780  Supplementary data.

  Comment: Biggin MD. "MyoD, a lesson in widespread DNA binding." Dev Cell. 2010 Apr 20;18(4):505-6. PMID: 20412764

• Gorodkin, Hofacker, Torarinsson, Yao, Havgaard and Ruzzo. De novo prediction of structured RNAs from genomic sequences. Trends in Biotechnology; Volume 28, Issue 1, 9-19, Jan., 2010. (Feature Review) PMID: 19942311 Supplement

• Tseng, Weinberg, Gore, Breaker and Ruzzo. Finding non-coding RNAs through genome-scale clustering. J Bioinform Comput Biol. 2009 Apr;7(2):373-88. PMID: 19340921. (Preliminary version: APBC '08, below.)

• Anandam, Torarinsson and Ruzzo. Multiperm: shuffling multiple sequence alignments while approximately preserving dinucleotide frequencies. Bioinformatics 25: 668-669 (2009). PMID: 19136551. Supplement and C++ source.

• Bar, Wyman, Fritz, Qi, Garg, Parkin, Kroh, Bendoraite, Mitchell, Nelson, Ruzzo, Ware, Radich, Gentleman, Ruohola-Baker, Tewari. MicroRNA Discovery and Profiling in Human Embryonic Stem Cells by Deep Sequencing of Small RNA Libraries. Stem Cells. Vol 26 No. 10 October 2008, pp. 2496-2505. PMID: 18583537 PubMed Central: PMC2847579 DOI: 10.1634/stemcells.2008-0356

• Weinberg, Regulski, Hammond, Barrick, Yao, Ruzzo, Breaker. The aptamer core of SAM-IV riboswitches mimics the ligand-binding site of SAM-I riboswitches. RNA. Mar, 2008, 14:822-828. PMID: 18369181

• Regulski, Moy, Weinberg, Barrick, Yao, Ruzzo, Breaker. A widespread riboswitch candidate that controls bacterial genes involved in molybdenum cofactor and tungsten cofactor metabolism. Mol Microbiol. 2008 Mar 19 [Epub ahead of print] PMID: 18363797

• Torarinsson, Yao, Wiklund, Bramsen, Hansen, Kjems, Tommerup, Ruzzo and Gorodkin. Comparative genomics beyond sequence based alignments: RNA structures in the ENCODE regions. Genome Research, Feb 2008, 18(2):242-251 PMID: 18096747

• Tseng, Weinberg, Gore, Breaker and Ruzzo. Finding non-coding RNAs through genome-scale clustering. Sixth Asia-Pacific Bioinformatics Conference, January 2008.

• Wang, Ruzzo and Tompa. How accurately is ncRNA aligned within whole-genome multiple alignments? BMC Bioinformatics 2007, 8:417. PMID: 17963514 Supplement.

• Yao, Jaeger, Ruzzo, Morales, Emond, Francke, Milewicz, Schwartz, Mulvihill. A Marfan syndrome gene expression phenotype in cultured skin fibroblasts. BMC Genomics 2007, 8:319 (12 September 2007) PMID: 17850668

• Weinberg, Barrick, Yao, Roth, Kim, Gore, Wang, Lee, Block, Sudarsan, Neph, Tompa, Ruzzo and Breaker. Identification of 22 candidate structured RNAs in bacteria using the CMfinder comparative genomics pipeline. Nucl. Acids Res., July 2007 35: 4809-4819. PMID: 17621584 Supplement

  Of the 7 motifs deemed most likely to be riboswitches, 5 have been experimentally verified: Weinberg, et al. 2008 (above), Regulski, et al. 2008 (above), Sudarsan, et al., Science, 2008, Wang, et al. Mol Cell., 2008, and Meyer, et al. RNA, 2008.

• Yao, Barrick, Weinberg, Neph, Breaker, Tompa and Ruzzo. A Computational Pipeline for High Throughput Discovery of cis-Regulatory Noncoding RNA in Prokaryotes. PLoS Computational Biology. 3(7): e126, July 6, 2007. doi:10.1371/journal.pcbi.0030126. Supplement PMID: 17616982

• Eisen, Coyne, Wu, Wu, Thiagarajan, Wortman, Badger, Ren, Amedeo, Jones, Tallon, Delcher, Salzberg, Silva, Haas, Majoros, Farzad, Carlton, Smith, Garg, Pearlman, Karrer, Sun, Manning, Elde, Turkewitz, Asai, Wilkes, Wang, Cai, Collins, Stewart, Lee, Wilamowska, Weinberg, Ruzzo, Wloga, Gaertig, Frankel, Tsao, Gorovsky, Keeling, Waller, Patron, Cherry, Stover, Krieger, Toro, Ryder, Williamson, Barbeau, Hamilton and Orias, Macronuclear genome sequence of the ciliate Tetrahymena thermophila, a model eukaryote. PLoS Biol 4(9): e286, Sep 2006. [See also: Synopsis, and ncRNA Supplementary Data.] PMID: 16933976

• Yao, Weinberg and Ruzzo. CMfinder--A Covariance Model Based RNA Motif Finding Algorithm. Bioinformatics, 2006, 22(4): 445-452. PMID: 16357030 Supplement

• Weinberg and Ruzzo: Sequence-based heuristics for faster annotation of non-coding RNA families. Bioinformatics, 2006, 22(1):35-39. PMID: 16267089 Supplement

• Yao and Ruzzo: A regression-based K nearest neighbor algorithm for gene function prediction from heterogeneous data. BMC Bioinformatics 7(Suppl 1):S11, 20 March 2006 PMID: 16723004

• Hsieh, Kenagy, Mulvihill, Jeanette, Wang, Chang, Yao, Ruzzo, Justice, Hudkins, Alpers, Berceli, and Clowes: Bone morphogenetic protein 4: potential regulator of shear stress-induced graft neointimal atrophy. Journal of Vascular Surgery, 43(1), Jan 2006, 150-158. Abstract and Supplementary Data. PMID: 16414402

• Barrick, Sudarsan, Weinberg, Ruzzo and Breaker: 6S RNA is a widespread regulator of eubacterial RNA polymerase that resembles an open promoter. RNA. 2005 May;11(5):774-84. (Epub 2005 Apr 5.) PMID: 15811922

• Mandal, Lee, Barrick, Weinberg, Emilsson, Ruzzo, and Breaker: A Glycine-dependent Riboswitch that Uses Cooperative Binding to Control Gene Expression in Bacteria. Science, 2004 Oct 8;306(5694):275-9. PMID: 15472076 Correction.
  • Abstract
  • Science Perspectives: "RNAs turn on in tandem" by Michael Famulok Science. 2004 Oct 8;306(5694):233-4.
  • "A Sophisticated Riboswitch", Sci. STKE 2004 (254), tw369. [DOI: 10.1126/stke.2542004tw369]
  • Faculty of 1000

• Mulvihill, Jaeger, Sengupta, Ruzzo, Reimer, Lukito and Schwartz: Atherosclerotic Plaque Smooth Muscle Cells Have a Distinct Phenotype.
  Arteriosclerosis, Thrombosis, and Vascular Biology, 24(7):1283-9, July 2004. PMID: 15142862
  • Abstract and Supplementary Data

• Weinberg and Ruzzo: Exploiting Conserved Structure for Faster Annotation of Non-coding RNAs Without Loss of Accuracy.
  Bioinformatics, 20 (suppl_1) i334-i341, 2004 and 12th International Conference on Intelligent Systems for Molecular Biology (ISMB 2004) , July 2004, Glasgow, Scottland. PMID: 15262817
  • Preprint: Abstract PDF Supplementary Data

• Weinberg and Ruzzo: Faster Genome Annotation of Non-coding RNA Families Without Loss of Accuracy.
  Eighth Annual International Conference on Research in Computational Molecular Biology (RECOMB 2004) , pp 243-251, March 2004, San Diego, CA.
  • Preprint: Abstract PDF Supplementary Data

• Jaeger, Sengupta and Ruzzo: Improved Gene Selection For Classification Of Microarrays.
  Pacific Symposium on Biocomputing, Kauai, Hawaii, Jan., 2003. PMID: 12603017
  • Preprint: Abstract PDF
  • Slides: PDF

• Barrett, Yeung, Ruzzo, Hsu, Blount, Sullivan, Zarbl, Delrow, Rabinovitch and Reid: Transcriptional Analyses of Barrett's Metaplasia and Normal Upper GI Mucosae. Neoplasia, March/April 2002, vol. 4, no. 2 pp. 121-128. PMID: 11896567

• Patterson, Yasuhara, and Ruzzo: Pre-mRNA Secondary Structure Prediction Aids Splice Site Prediction.
  Pacific Symposium on Biocomputing, Kauai, Hawaii, Jan., 2002, pp. 223-234. PMID: 11928478
  • Preprint: Abstract PDF

• Yeung, Fraley, Murua, Raftery, and Ruzzo: Model-Based Clustering and Data Transformations for Gene Expression Data. (Highlighted by ISI as a "Fast Moving Fronts" paper and as a "New Hot Paper".)
  • Bioinformatics, 17 (10) 977-987 (2001) PMID: 11673243, and The Third Georgia Tech-Emory International Conference on Bioinformatics, Atlanta, GA, Nov. 2001.
  • Preprint: Abstract   PDF
  • Supplementary Information.
  • Preliminary version: Technical Report UW-CSE-2001-04-02, April, 2001. (Also UW Stat. Dept. TR 396.)
    Abstract PDF

• Yeung and Ruzzo: Principal component analysis for clustering gene expression data.
  • Bioinformatics, 17 (9) 763-774 (2001) PMID: 11590094.
  • Preprint: Abstract   PDF
  • Supplementary Information
  • Preliminary version: Technical Report UW-CSE-00-11-03, November, 2000.
    Abstract PDF

• Yeung, Barrett, Delrow, Blount, Hsu, Ruzzo, Reid and Rabinovitch: Expression analysis of Barrett's epithelium and normal gastrointestinal tissues.  Technical Report UW-CSE-2000-11-01, November 2000.
  Abstract PDF

• Keller, Schummer, Hood, Ruzzo: Bayesian Classification of DNA Array Expression Data. Technical Report UW-CSE-2000-08-01, August, 2000.
  Abstract PDF

• Yeung, Haynor, Ruzzo: Validating Clustering for Gene Expression Data. (An ISI "Fast-Breaking Paper".)
  • Bioinformatics, 2001 v 17 #4: 309-318, PMID: 11301299.
  • Preprint and Supplementary Information.
  • Technical Report UW-CSE-00-01-01, January 2000.
    Abstract PostScript PDF

• Redstone, Ruzzo: Algorithms for a Simple Point Placement Problem. Algorithms and Complexity, 4th Italian Conference, CIAC 2000, Rome, Italy, March 2000, pp. 32-43.
  Abstract PostScript PDF Conference Proceedings

• Ruzzo, Tompa: A Linear Time Algorithm for Finding All Maximal Scoring Subsequences. Seventh International Conference on Intelligent Systems for Molecular Biology, Heidelberg, Germany, August 1999, pp. 234-241, PMID: 10786306.
  Abstract PostScript PDF

• Redstone, Ruzzo: Algorithms for Ordering DNA Probes on Chromosomes. Technical Report UW-CSE-98-12-04.
  Abstract PostScript PDF

Computational Complexity Theory

• Dymond, Ruzzo: Parallel RAMs with Owned Global Memory and Deterministic Context-Free Language Recognition JACM, Vol 47, #1, (Jan. 2000) 16-45. (Preliminary version: Technical Report UW-CSE-97-02-03.)

• Beame, Borodin, Raghavan, Ruzzo, Tompa: A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata, SIAM Journal on Computing, Vol 28, #3 1999, 1051-1072.

• Barnes, Buss, Ruzzo, Schieber: A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity, SIAM Journal on Computing, Vol 27, #5, Oct. 1998, 1273-1282.

• Chandra, Raghavan, Ruzzo, Smolensky, Tiwari: The Electrical Resistance of a Graph Captures its Commute and Cover Times, Computational Complexity, Vol 6, #4, (1997) 312-340. (Preliminary version: PostScript PDF.)

• Barnes, Ruzzo: Deterministic Algorithms for Undirected s-t Connectivity Using Polynomial Time and Sublinear Space, Computational Complexity, Vol 6, #1 (1996-1997) 1-28. (Preliminary version: UW-CSE-91-06-02.)

• Beame, Borodin, Raghavan, Ruzzo, Tompa: Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata, Information and Computation, Vol 130, #2, Nov. 1996, pp 101-129. (Preliminary version: PostScript PDF.)

• Dymond, Fich, Nishimura, Ragde, Ruzzo: Pointers versus Arithmetic in PRAMs, Journal of Computer and System Sciences, Vol 53, #2 (Oct. 1996) 218-232. (Preliminary version: UW-CSE-93-03-06.)

• Greenlaw, Hoover, Ruzzo: Limits to Parallel Computation, Oxford, 1995. (PDF).
  See also: Updates and Errata and: Greenlaw, Hoover, Miyano, Ruzzo, Shiraishi and Shoudai: The Parallel Computation Project.

• Ruzzo: On uniform circuit complexity, Journal of Computer and System Sciences Volume 22, Issue 3, June 1981, Pages 365-383.

• Ruzzo: Tree-size bounded alternation, Journal of Computer and System Sciences, Volume 21, Issue 2, October 1980, Pages 218-235.

• Ruzzo: Complete Pushdown Languages, 1979. (Unpublished manuscript.)

E-mail: