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