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
