Special-purpose hardware for fast comparison of DNA and/or protein sequences

[wrp at biochsn.acc.virginia.edu]

In article <34608 at mimsy.umd.edu> watt at 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 at umiacs.umd.edu		     Phillip Curtiss
  UUCP:	uunet!mimsy!curtiss		UMIACS - Univ. of Maryland
 Phone:	+1-301-405-6710			  College Park, Md 20742