source: branches/profile/SL/PRONUC/AP_pro_a_nucs.cxx

Last change on this file was 12667, checked in by westram, 11 years ago
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 14.9 KB
Line 
1// =============================================================== //
2//                                                                 //
3//   File      : AP_pro_a_nucs.cxx                                 //
4//   Purpose   :                                                   //
5//                                                                 //
6//   Institute of Microbiology (Technical University Munich)       //
7//   http://www.arb-home.de/                                       //
8//                                                                 //
9// =============================================================== //
10
11#include "AP_pro_a_nucs.hxx"
12
13#include <AP_codon_table.hxx>
14#include <arbdbt.h>
15#include <ad_cb.h>
16#include <arb_str.h>
17#include <algorithm>
18
19#define pn_assert(cond) arb_assert(cond)
20
21char *AP_create_dna_to_ap_bases() {
22    int       i;
23    AP_BASES  val;
24    char     *table = new char[256];
25
26    for (i=0; i<256; i++) {
27        switch ((char)i) {
28            case 'a': case 'A': val = AP_A; break;
29            case 'g': case 'G': val = AP_G; break;
30            case 'c': case 'C': val = AP_C; break;
31            case 't': case 'T':
32            case 'u': case 'U': val = AP_T; break;
33            case 'n': case 'N': val = (AP_BASES)(AP_A + AP_G + AP_C + AP_T); break;
34            case '?': case '.': val = (AP_BASES)(AP_A + AP_G + AP_C + AP_T + AP_S); break;
35            case '-': val = AP_S; break;
36            case 'm': case 'M': val = (AP_BASES)(AP_A+AP_C); break;
37            case 'r': case 'R': val = (AP_BASES)(AP_A+AP_G); break;
38            case 'w': case 'W': val = (AP_BASES)(AP_A+AP_T); break;
39            case 's': case 'S': val = (AP_BASES)(AP_C+AP_G); break;
40            case 'y': case 'Y': val = (AP_BASES)(AP_C+AP_T); break;
41            case 'k': case 'K': val = (AP_BASES)(AP_G+AP_T); break;
42            case 'v': case 'V': val = (AP_BASES)(AP_A+AP_C+AP_G); break;
43            case 'h': case 'H': val = (AP_BASES)(AP_A+AP_C+AP_T); break;
44            case 'd': case 'D': val = (AP_BASES)(AP_A+AP_G+AP_T); break;
45            case 'b': case 'B': val = (AP_BASES)(AP_C+AP_G+AP_T); break;
46            default: val = AP_N; break;
47        }
48        table[i] = (char)val;
49    }
50    return table;
51}
52
53long *AWT_translator::create_pro_to_bits() const {
54    int i;
55    int j;
56    long *table = (long *)GB_calloc(sizeof(long), 256);
57    for (i = 0;   i < max_aa; i++) {
58        j = index_2_spro[i];
59        if (j == '.') {
60            table[i] = -1;
61            continue;
62        }
63        j = s2str[j]->index;
64        table[i] = 1<<j;
65    }
66    return table;
67}
68
69void AWT_translator::build_table(unsigned char pbase, const char *tri_pro, const char *nuc) {
70    struct arb_r2a_pro_2_nuc  *str = s2str[pbase];
71
72    // search for existing protein, else generate new
73    if (!str) {
74        str                               = new arb_r2a_pro_2_nuc;
75        s2str[pbase]          = str;
76        s2str[tolower(pbase)] = str;
77
78        str->index      = max_aa++;
79        str->single_pro = pbase;
80        str->tri_pro[0] = tri_pro[0];
81        str->tri_pro[1] = tri_pro[1];
82        str->tri_pro[2] = tri_pro[2];
83
84        index_2_spro[str->index] = pbase;
85    }
86    // fast hash table
87    GBS_write_hash(t2i_hash, nuc, pbase);
88
89    int n0 = nuc_2_bitset[safeCharIndex(nuc[0])];
90    int n1 = nuc_2_bitset[safeCharIndex(nuc[1])];
91    int n2 = nuc_2_bitset[safeCharIndex(nuc[2])];
92
93    struct arb_r2a_pro_2_nucs *nucs;
94    for (nucs = str->nucs; nucs; nucs = nucs->next) {
95        if ((!(nucs->nucbits[0] & ~n0)) &&      // search superset
96            (!(nucs->nucbits[1] & ~n1)) &&
97            (!(nucs->nucbits[2] & ~n2))) break;
98
99        int c = 0;
100        if (nucs->nucbits[0] != n0) c++;
101        if (nucs->nucbits[1] != n1) c++;
102        if (nucs->nucbits[2] != n2) c++;
103        if (c <= 1) break;
104    }
105    if (!nucs) {
106        nucs       = new arb_r2a_pro_2_nucs;
107        nucs->next = str->nucs;
108        str->nucs  = nucs;
109    }
110    nucs->nucbits[0] |= n0;
111    nucs->nucbits[1] |= n1;
112    nucs->nucbits[2] |= n2;
113}
114
115// ----------------------------
116//      arb_r2a_pro_2_nucs
117
118arb_r2a_pro_2_nucs::arb_r2a_pro_2_nucs()
119    : next(0)
120{
121    memset(nucbits, 0, sizeof(nucbits));
122}
123arb_r2a_pro_2_nucs::~arb_r2a_pro_2_nucs() {
124    delete next;
125}
126
127// ---------------------------
128//      arb_r2a_pro_2_nuc
129
130arb_r2a_pro_2_nuc::arb_r2a_pro_2_nuc()
131    : single_pro(0)
132    , index(0)
133    , nucs(0)
134{
135    memset(tri_pro, 0, sizeof(tri_pro));
136}
137arb_r2a_pro_2_nuc::~arb_r2a_pro_2_nuc() {
138    delete nucs;
139}
140
141// ------------------------
142//      AWT_translator
143
144static int codon_defined_in(const char *codon, const char *codons) {
145    for (int off=0; codons[off]; off+=3) {
146        if (codon[0]==codons[off] && codon[1]==codons[off+1] && codon[2]==codons[off+2]) {
147            return 1;
148        }
149    }
150    return 0;
151}
152
153// order of tables generated with build_table() by AWT_translator ctor is important:
154// must be compatible with DIST/PH_protdist.cxx !!
155// except that this table has an 's' insertion !!!
156
157#define T2I_ENTRIES_MAX 196 // maximum number of generated translations (by code number 11)
158
159AWT_translator::AWT_translator(int arb_protein_code_nr) :
160    distance_meter(0),
161    code_nr(arb_protein_code_nr),
162    pro_2_bitset(0),
163    realmax_aa(0),
164    max_aa(0)
165{
166    memset(s2str, 0, sizeof(s2str));
167    memset(index_2_spro, 0, sizeof(index_2_spro));
168
169    nuc_2_bitset = AP_create_dna_to_ap_bases();
170    t2i_hash     = GBS_create_hash(T2I_ENTRIES_MAX, GB_IGNORE_CASE); // case insensitive
171
172    AP_initialize_codon_tables();
173
174    {
175        char *D_codons = strdup(AP_get_codons('D', code_nr));
176        char *N_codons = strdup(AP_get_codons('N', code_nr));
177        char *E_codons = strdup(AP_get_codons('E', code_nr));
178        char *Q_codons = strdup(AP_get_codons('Q', code_nr));
179
180        char protein;
181        for (protein='*'; protein<='Z'; protein = (protein=='*' ? 'A' : protein+1)) {
182            if (protein!='J' && protein!='O' && protein!='U') { // JOU are no aminos
183                const char *codons;
184                if (protein=='D')   codons = D_codons;
185                else if (protein=='N')  codons = N_codons;
186                else if (protein=='E')  codons = E_codons;
187                else if (protein=='Q')  codons = Q_codons;
188                else            codons = AP_get_codons(protein, code_nr);
189                // codons now contains a 0-terminated-string containing all possible codons for protein
190
191                const char *protein_name = AP_get_protein_name(protein);
192
193                for (int off=0; codons[off]; off+=3) {
194                    char codon[4];
195                    memcpy(codon, codons+off, 3);
196                    codon[3] = 0;
197
198                    if (protein=='B') {
199                        if (!codon_defined_in(codon, D_codons) && !codon_defined_in(codon, N_codons)) {
200                            build_table(protein, protein_name, codon);
201                        }
202                    }
203                    else if (protein=='Z') {
204                        if (!codon_defined_in(codon, E_codons) && !codon_defined_in(codon, Q_codons)) {
205                            build_table(protein, protein_name, codon);
206                        }
207                    }
208                    else {
209                        build_table(protein, protein_name, codon);
210                    }
211                }
212            }
213        }
214
215        free(Q_codons);
216        free(E_codons);
217        free(N_codons);
218        free(D_codons);
219    }
220
221    realmax_aa = max_aa;
222
223    build_table('-', "---", "---");
224    build_table('.', "...", "...");
225    build_table('.', "???", "???");
226    build_table('X', "NNN", "NNN");
227
228    pn_assert(GBS_hash_count_elems(t2i_hash) <= T2I_ENTRIES_MAX);
229
230    pro_2_bitset = create_pro_to_bits();
231}
232
233AWT_translator::~AWT_translator() {
234    free(pro_2_bitset);
235
236    delete [] nuc_2_bitset;
237    GBS_free_hash(t2i_hash);
238    for (int i=0; i<256; i++) {
239        if (i != tolower(i)) continue; // do not delete duplicated entries (a-z == A-Z!)
240        delete s2str[i];
241    }
242
243    delete distance_meter;
244}
245
246const AWT_distance_meter *AWT_translator::getDistanceMeter() const {
247    if (!distance_meter) distance_meter = new AWT_distance_meter(this);
248    return distance_meter;
249}
250
251
252// ----------------------------
253//      Distance functions
254
255static int nuc_dist(const AWT_translator *translator, unsigned char p1, unsigned char p2) {
256    // calculate minimum necessary nucleotide-mutations for a given amino-acid-mutation
257
258    const struct arb_r2a_pro_2_nuc *s1, *s2;
259    s1                                      = translator->S2str(p1);
260    s2                                      = translator->S2str(p2);
261    if ((!s1) || (!s2)) return -1;
262    struct arb_r2a_pro_2_nucs      *n1, *n2;
263    long                            mindist = 3;
264    // Check all combinations, if any combination is valid -> zero distance
265    for (n1 = s1->nucs; n1; n1=n1->next) {
266        for (n2 = s2->nucs; n2; n2=n2->next) {
267            int dist = 0;
268            int i;
269            for (i=0; i<3; i++) {
270                if (n1->nucbits[i] & n2->nucbits[i]) continue;
271                dist++;
272            }
273            if (dist< mindist) mindist = dist;
274        }
275    }
276    return mindist;
277}
278
279#if defined(DEBUG)
280static void awt_pro_a_nucs_debug(const AWT_translator *translator, const AWT_distance_meter *distmeter) {
281    int max_aa     = translator->MaxAA();
282    int realmax_aa = translator->RealmaxAA();
283
284    for (int s = 0; s< max_aa; s++) {
285        const AWT_PDP *dist = distmeter->getDistance(s);
286
287        // check bits should not be present in distpad
288        if (s<realmax_aa) {
289            for (int i=0; i<2; i++) {
290                // assertion: bit is set in patd[i] -> bit is clear in patd[i+1]
291                assert_or_exit((dist->patd[i] & ~dist->patd[i+1]) == 0);
292            }
293        }
294        printf("Base %c[%i]: Dist to ", translator->Index2Spro(s), s);
295        for (int d = 0; d< max_aa; d++) {
296            int i;
297            for (i=0; i<3; i++) {
298                if (dist->patd[i] & (1<<d)) break;
299            }
300            printf ("%c%i ", translator->Index2Spro(d), i);
301        }
302        printf ("\n");
303    }
304}
305#endif // DEBUG
306
307// ----------------------------
308//      AWT_distance_meter
309
310AWT_distance_meter::AWT_distance_meter(const AWT_translator *translator) {
311    memset(dist_, 0, sizeof(dist_));
312    memset(transform07, 0, sizeof(transform07));
313    memset(transform815, 0, sizeof(transform815));
314    memset(transform1623, 0, sizeof(transform1623));
315
316    int s;
317    int i;
318    int max_aa     = translator->MaxAA();
319    int realmax_aa = translator->RealmaxAA();
320
321    for (s = 0; s< max_aa; s++) {
322        dist_[s] = (AWT_PDP *)calloc(sizeof(AWT_PDP), max_aa);
323
324        const arb_r2a_pro_2_nuc *s2str = translator->S2str(translator->Index2Spro(s));
325        for (i=0; i<3; i++) {
326            dist_[s]->nucbits[i] = s2str->nucs->nucbits[i];
327        }
328    }
329
330    for (s = 0; s< max_aa; s++) {
331        for (int d = 0; d< realmax_aa; d++) {
332            int dist = nuc_dist(translator, translator->Index2Spro(s), translator->Index2Spro(d));
333
334            if (dist==0) dist_[s]->patd[0] |= 1<<d; // distance == 0
335            if (dist<=1) dist_[s]->patd[1] |= 1<<d; // distance <= 1
336        }
337        dist_[s]->patd[2] |= dist_[s]->patd[1]; // (distance <= 1) => (distance <= 2)
338        dist_[s]->patd[0] |= 1<<s; // set 'distance to self' == 0
339    }
340
341    for (s = 0; s< max_aa; s++) {
342        long sum = 0;
343        for (int d = 0; d< realmax_aa; d++) {
344            if ((1 << d) & dist_[s]->patd[1]) {   // if distance(s, d) <= 1
345                sum |= dist_[d]->patd[1]; // collect all proteins which have 'distance <= 1' to 'd'
346            }
347        }
348        dist_[s]->patd[2] |= sum; // and store them in 'distance <= 2'
349    }
350
351    for (i=0; i<256; i++) {
352        for (s = 0; s<8; s++) {
353            if (i & (1<<s)) {
354                transform07[i]   |= dist_[s]->patd[1];
355                transform815[i]  |= dist_[s+8]->patd[1];
356                transform1623[i] |= dist_[s+16]->patd[1];
357            }
358        }
359    }
360#ifdef DEBUG
361    awt_pro_a_nucs_debug(translator, this);
362#endif
363}
364
365AWT_distance_meter::~AWT_distance_meter() {
366    for (int i=0; i<64; i++) {
367        delete dist_[i];
368    }
369
370}
371
372// --------------------------------------------------------------------------------
373// Translator factory:
374
375static int current_user_code_nr = -1;                // always contain same value as AWAR_PROTEIN_TYPE (after calling AWT_default_protein_type once)
376
377static void user_code_nr_changed_cb(GBDATA *gb_awar) {
378    // this callback keeps 'current_user_code_nr' synced with AWAR_PROTEIN_TYPE
379    GBDATA         *gb_main = GB_get_root(gb_awar);
380    GB_transaction  ta(gb_main);
381    current_user_code_nr    = GB_read_int(gb_awar);
382}
383
384#define CACHED_TRANSLATORS 4
385
386AWT_translator *AWT_get_translator(int code_nr) {
387    static SmartPtr<AWT_translator> cached[CACHED_TRANSLATORS];
388
389    if (cached[0].isNull() || cached[0]->CodeNr() != code_nr) { // most recent != requested
390        SmartPtr<AWT_translator> translator;
391
392        int i;
393        for (i = 1; i<CACHED_TRANSLATORS; i++) {
394            if (cached[i].isSet() && cached[i]->CodeNr() == code_nr) {
395                // found existing translator
396                translator = cached[i];
397                cached[i].SetNull();
398                break;
399            }
400        }
401
402        if (translator.isNull()) {
403            translator = new AWT_translator(code_nr);
404        }
405
406        // insert new or found translator at front and shift existing to higher indices:
407        for (i = 0; i<CACHED_TRANSLATORS && translator.isSet(); i++) {
408            std::swap(cached[i], translator);
409        }
410
411        // deletes oldest translator,  if no empty array position was found:
412    }
413
414    pn_assert(cached[0]->CodeNr() == code_nr);
415    return &*cached[0];
416}
417
418int AWT_default_protein_type(GBDATA *gb_main) {
419    // returns protein code selected in AWAR_PROTEIN_TYPE
420
421    if (current_user_code_nr == -1) { // user protein code in AWAR_PROTEIN_TYPE not traced yet
422        pn_assert(gb_main != 0); // either pass gb_main here or call once with valid gb_main at program startup
423
424        {
425            GB_transaction ta(gb_main);
426            GBDATA *awar = GB_search(gb_main, AWAR_PROTEIN_TYPE, GB_INT);
427            GB_add_callback(awar, GB_CB_CHANGED, makeDatabaseCallback(user_code_nr_changed_cb)); // bind a callback that traces AWAR_PROTEIN_TYPE
428            user_code_nr_changed_cb(awar);
429        }
430
431        pn_assert(current_user_code_nr != -1);
432    }
433
434    return current_user_code_nr;
435}
436
437AWT_translator *AWT_get_user_translator(GBDATA *gb_main) {
438    return AWT_get_translator(AWT_default_protein_type(gb_main));
439}
440
441// --------------------------------------------------------------------------------
442
443#ifdef UNIT_TESTS
444#ifndef TEST_UNIT_H
445#include <test_unit.h>
446#endif
447
448static int test_code_nr = -1;
449static void translator_instance() {
450    AWT_translator instance(test_code_nr);
451}
452
453void TEST_translator_instantiation() {
454    for (int i = 0; i<AWT_CODON_TABLES; ++i) {
455        TEST_ANNOTATE(GBS_global_string("i=%i", i));
456        test_code_nr = i;
457        TEST_EXPECT_NO_SEGFAULT(translator_instance);
458    }
459}
460
461#endif // UNIT_TESTS
462
463// --------------------------------------------------------------------------------
Note: See TracBrowser for help on using the repository browser.