Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!spool.mu.edu!news.nd.edu!mentor.cc.purdue.edu!purdue!haven.umd.edu!mimsy!eleazar.dartmouth.edu!watt
From: watt@eleazar.dartmouth.edu
Newsgroups: bionet.biology.computational
Subject: Re: Special-purpose hardware for fast comparison of DNA and/or protein sequences
Message-ID: <34608@mimsy.umd.edu>
Date: 17 May 91 15:22:25 GMT
Article-I.D.: mimsy.34608
Sender: news@mimsy.umd.edu
Distribution: bionet
Organization: Dartmouth College, Hanover, NH
Lines: 49
Approved: comp-bio-moderator@genbank.bio.net


howdy,

I am currently working on a simple NuBus board for the MacII to 
implement the Needleman-Wunsch algorithm as my M.S. thesis.  
I will also be writing the user-interface software that will do 
some basic color dot-plot homologies.  

The architecture is not all that sophisticated: I have a single
Actel FPGA to do the additions and comparisons and a lot of 
DRAM to store the array for extracting the resulting alignment 
by backtracking through the array.  

The project is not meant to push back the frontiers of string
comparison computer architecture, but rather to bring some of
the advances in hardware to the lab at a reasonable cost.  
The algorithm is still O(N^2), but the curve is stretched out
some.  I am hoping for a 50x speedup over my plain vanilla IIfx.  

At the moment I am working on the schematic capture and simulation
phase of the design and hope to go to prototype within a month. 

I am a hardware designer, not a biologist, and I still have some
doubts about the features of my board, so if you have any 
suggestions, I would love to hear them.  

At the moment the design has the following features:

	User settable (in Mac software) costs (integers 0-15) for
		Insertion gap creation
		Insertion of a single nucleotide
		Deletion gap creation
		Deletion of a single nucleotide
		Substitution of a single nucleotide.

	Memory space for sequences up to 
		4000 x 4000 nts. with 1Mb SIMMs
		8000 x 8000 nts. with 4Mb SIMMs
		16000 x 16000 nts. with 16Mb SIMMs

	Ability to calculate 8000 x 8000 in approx. 6 seconds.

Thanks for your time.

--
                                --- Moderator ---
Domain: curtiss@umiacs.umd.edu		     Phillip Curtiss
  UUCP:	uunet!mimsy!curtiss		UMIACS - Univ. of Maryland
 Phone:	+1-301-405-6710			  College Park, Md 20742