Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sdd.hp.com!spool.mu.edu!news.nd.edu!mentor.cc.purdue.edu!purdue!haven.umd.edu!mimsy!biochsn.acc.virginia.edu!wrp
From: wrp@biochsn.acc.virginia.edu
Newsgroups: bionet.biology.computational
Subject: Re: Special-purpose hardware for fast comparison of DNA and/or protein sequences
Message-ID: <1991May17.183743.17888@murdoch.acc.Virginia.EDU>
Date: 17 May 91 18:37:43 GMT
Article-I.D.: murdoch.1991May17.183743.17888
Sender: news@mimsy.umd.edu
Distribution: bionet
Organization: University of Virginia
Lines: 38
Approved: comp-bio-moderator@genbank.bio.net

In article <34608@mimsy.umd.edu> watt@eleazar.dartmouth.edu writes:
>

>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.  
>
>
>	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.
>

	It should be noted that efficient implementations of both
rigorous global similarity calculations (Needleman Wunsch) and local
similarity calculations (Smith-Waterman, Waterman-Eggert) that require
only linear (O(N)) space have been described by Miller and Myers
(CABIOS 1988 4:11-17) and Huang and Miller (CABIOS, 1990 6:373-381,
Adv. Appl. Math, 1991, in press).

	It seems silly to place memory restrictions on the algorithm
when none are necessary.

Bill Pearson
--
                                --- 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