Re: A86: lookup table

[Prev][Next][Index][Thread]

Re: A86: lookup table


At 06:33 1999-06-04 -0700, you wrote:
>
>Could someone give me a well-commented example of an efficient
>lookup-table routine?  I have a program that decodes DNA codons and
>displays what amino acids they code for, so I have to look up
>three-letter strings, made up of any combination of the letters C,G,A,
>and T, and match them to the address of a string (the name of the amino)
>to display.  At first I was going to use a long list of CP's, but I've
>done that in past programs and it is not only slow but also very space
>consuming.  Is there a smaller, faster routine that could do the same?

If I understood this correctly, you want from the input (ex GAC) a
string with the name returned? This is easiest done with numbering the letters
C, G, A and T as 0, 1, 2, 3, and then have a table with 4^3 pointers:

; Input:  HL -> three letter string (uppercase)
; Output: NC, HL -> string
;         CF = error in input string
Convert:
 ex de,hl
 ld bc,$0300 ; B = no of letters, C = acid no
 ; Loop through the three letters to convert the string to a number
 ; between 0-63 (CCC=0, CCG=1, ... TTT=63)
GetAcidNo:
 push bc
 ld a,(de) ; Get next letter in string
 inc de
 ld hl,letters
 ld bc,4   ; Four valid letters
 cpir   ; This one is fast...
 ld h,c ; H = letter no (0<=h<=3)
 pop bc
 scf
 ret nz ; If the letter is none of C, G, A and T, set carry and return
 ld a,c
 add a,a
 add a,a
 add a,h
 ld c,a ; acid=acid*4+letter
 djnz GetAcidNo
 ld h,0
 ld l,a
 add hl,hl ; Each ptr is 2 bytes
 ld de,ptrTable
 add hl,de
 call _ldhlind  ; LD HL,(HL) == ld a,(hl) \ inc hl \ ld h,(hl) \ ld l,a
 or a  ; Clear carry - operation succesful
 ret

letters:
 .db "TAGC"  ; Backwards, so C=0, G=1, A=2, T=3

ptrTable:
 .dw CCC,CCG,CCA,CCT
 .dw CGC,CGG,CGA,CGT
 ...

CCC:
 .db "Name of CCC",0
CCF:
 .db "Name of CCG",0


Of course, if several of the letter combinations are the same acid,
you point them to the same string.

Although this method requires a 128 byte pointer table, it's definately
_FAST_. Instead of the ptrtable, you could line up all 64 strings
after each other, and scan through the strings (xor a \ cpir) C times.
Slower, but you save 128 bytes (but you _must_ have 64 strings, even
if many of the them are the same).

--
Jimmy Mårdell                  "Applications programming is a race between
mailto:yarin@acc.umu.se         software engineers, who strive to produce
http://www.acc.umu.se/~yarin/   idiot-proof programs, and the Universe
ICQ #: 14193765                 which strives to produce bigger idiots."
Follow-Ups: References: