POCKET ARITHMETIC AND NEEDLEMAN-WUNSCH ON CRAY RESEARCH COMPUTERS

In the interest of providing more efficient computer-based analysis of DNA and protein sequences, Cray Research has developed a high performance implementation of the sequence alignment method of Needleman and Wunsch using the programming technique of pocket arithmetic. The basis for this implementation is the program SEQHDP, which finds locally homologous subsequences of a protein sequence pair and determines the statistical significance of the homology. Pocket arithmetic takes advantage of the 64-bit width of an operand on the Cray Y-MP by packing more than one integer value per word, then performing logical or integer operations on the packed word to yield multiple results per operation. This technique, in combination with the vector processing capabilities of the Cray Y-MP CPU, produces substantially improved performance over the conventionally coded version of the same algorithm. We will introduce the programming technique of pocket arithmetic, then describe its implementation in the Needleman-Wunsch sequence comparison function in SEQHDP. Performance results based on actual protein sequence comparisons are presented.