1package Bio::Tools::SeqPattern::Backtranslate;
2$Bio::Tools::SeqPattern::Backtranslate::VERSION = '1.7.7';
3use strict;
4use warnings;
5
6use base qw(Bio::Root::Root);
7use base qw(Exporter);
8
9=head1 NAME
10
11Bio::Tools::SeqPattern::Backtranslate - reverse translate protein patterns
12
13=head1 DESCRIPTION
14
15This module should not be used directly. It provides helper methods to
16Bio::Tools::SeqPattern to reverse translate protein patterns.
17
18=cut
19
20use Bio::Seq;
21use Bio::Tools::CodonTable;
22
23use List::MoreUtils qw(uniq);
24use Carp qw(croak);
25
26our @EXPORT_OK = qw(_reverse_translate_motif);
27
28our @EXPORT = @EXPORT_OK;
29
30sub _reverse_translate_motif {
31   # Main subroutine. It takes a Profam-like motif and returns its
32   # reverse translation using degenerate codons.
33
34   # Steps:
35   # 1. Tokenize, then parse tokens.
36   # 2. Reverse translate each token type.
37   # 3. Join tokens in original order. Return the resulting string.
38
39   my $motif = shift;
40
41   $motif =~ s/\./X/g;
42   $motif = uc $motif;
43
44   ### 1. Tokenize, parse the motif.
45   my ( $ordered, $classified ) = _parse_motif($motif);
46
47   ### 2. Reverse translate each token type.
48   # Reverse translate the plain (unambiguous) tokens.
49   my $ct = Bio::Tools::CodonTable->new;
50   foreach my $seq ( @{ $classified->{plain} } ) {
51      my $seqO
52          = Bio::Seq->new( -seq => $$seq, -alphabet => 'protein' );
53      $$seq = $ct->reverse_translate_all($seqO);
54   }
55
56   # Reverse translate the ambiguous tokens.
57   foreach my $token ( @{ $classified->{ambiguous} } ) {
58      my ($aas) = $$token =~ m(([A-Za-z\.]+));
59      my @codons_to_contract;
60
61      foreach my $residue ( split '', $aas ) {
62         push @codons_to_contract, $ct->revtranslate($residue);
63      }
64
65      my $ambiguous_codon = _contract_codons(@codons_to_contract);
66      $$token             = $ambiguous_codon;
67   }
68
69   # Reverse translate the negated residues.
70   foreach my $token ( @{ $classified->{negated} } ) {
71      my ($aas) = $$token =~ m(([A-Za-z\.]+));
72      my $ambiguous_codon = _negated_aas_to_codon($aas);
73      $$token = $ambiguous_codon;
74   }
75
76   ### 3. Join the profile back from its tokens.
77   return join '', map {$$_} @{$ordered};
78
79}
80
81sub _parse_motif {
82   # Profam-like motif parser. It takes the pattern as a string, and
83   # returns two data structures that contain the tokens, organized
84   # by order of appearance in the pattern (first return value) and by
85   # category (second return value).
86
87   my $motif = shift;
88   my $parser  = _tokenize_motif($motif);
89   my ( %tokens, @tokens );
90
91   while ( my $token = $parser->() ) {
92      croak ("Unknown syntax token: <", $token->[1], ">")
93          if ( $token->[0] eq 'UNKNOWN' );
94      push @{ $tokens{ $token->[0] } }, \$token->[1];
95      push @tokens, \$token->[1];
96   }
97   return ( \@tokens, \%tokens );
98}
99
100sub _tokenize_motif {
101
102   # Return a tokenizer iterator that sequentially recognizes and
103   # returns each token in the input pattern.
104   # Examples of each token type:
105
106   # ambiguous: a position with more than one possible residue.
107   #     eg. [ALEP]
108   # negated: a position in which some residues are excluded.
109   #     eg. [^WY]
110   # plain: a common sequence of residues. One position, one residue.
111   #     eg. MAAEIK
112   # open_par, close_par: tags surrounding a motif that is repeated
113   #     a certain number of times.
114   #     eg. (...){3}
115
116   my $target = shift;
117   return sub {
118      return [ 'ambiguous', $1 ]
119          if $target =~ /\G (\[[A-Za-z\.]+\])     /gcx;
120      return [ 'negated',   $1 ]
121          if $target =~ /\G (\[\^[A-Za-z\.]+\])   /gcx;
122      return [ 'plain',     $1 ]
123          if $target =~ /\G ([A-Za-z\.]+)         /gcx;
124      return [ 'open_par',  $1 ]
125          if $target =~ /\G (\()                  /gcx;
126      return [ 'close_par', $1 ]
127          if $target =~ /\G (\)[\{\d+[,\d+]*\}]*) /gcx;
128      return [ 'UNKNOWN',   $1 ]
129          if $target =~ /\G (.)                   /gcx;
130      return;
131   };
132}
133
134sub _contract_codons {
135
136   # Take a list of codons, return an ambiguous codon.
137   my @codons = map { uc $_ } @_;
138
139   my @by_letter = ( [], [], [], );
140   my $ambiguous_codon;
141   foreach my $codon (@codons) {
142      my @letters = split '', $codon;
143      for my $i ( 0 .. 2 ) {
144         push @{ $by_letter[$i] }, $letters[$i];
145      }
146   }
147   for my $i ( 0 .. 2 ) {
148      $ambiguous_codon
149          .= _convert( 'dna', _uniq_string( @{ $by_letter[$i] } ) );
150   }
151   return $ambiguous_codon;
152}
153
154sub _expand_codon {
155
156   # Given a degenerate codon, return a list with all its
157   # constituents. Takes a three-letter string (codon) as
158   # input, returns a list with three-letter scalars.
159
160   my $codon = shift;
161   die "Wrong codon length!\n" if length $codon != 3;
162
163
164   my ( @codons, @return_bases );
165   my @orig_bases = split '', $codon;
166
167   for my $i ( 0 .. 2 ) {
168
169      # from each redundant base, create a list with all their
170      # components (e.g., N -> (A, C, G, T) );
171      my @components = split '', _convert('dna', $orig_bases[$i] );
172      $orig_bases[$i] = [@components];
173   }
174
175   # Combine all the bases of each of the three positions of the
176   # codons, and build the return list.
177   for my $i ( @{ $orig_bases[0] } ) {
178      for my $j ( @{ $orig_bases[1] } ) {
179         for my $k ( @{ $orig_bases[2] } ) {
180            push @return_bases, $i . $j . $k;
181         }
182      }
183   }
184   return @return_bases;
185}
186
187{
188   my %convert;
189
190   sub _convert {
191      # Interconvert between redundant and non-redundant protein and
192      # dna alphabets. Takes an alphabet (protein or dna) and a string
193      # with the letter, and returns its equivalent in
194      # redundant/non-redundant alphabet. Example ACTG -> N.
195
196      my ($alphabet, $letter) = @_;
197      unless (
198         $alphabet and $alphabet =~ /^dna$|^protein$/i
199         and $letter and length $letter <= 4
200      ) { croak "Wrong arguments!\n"; }
201
202      unless (%convert) {
203         %convert = (
204            'dna' => {
205               qw(N ACGT B CGT D AGT H ACT V ACG K GT
206                   M AC R AG S CG W AT Y CT A A C C T T G G)
207            },
208            'protein' => {
209               '.' => 'ACDEFGHIJKLMNOPQRSTUVWY',
210               X   => 'ACDEFGHIJKLMNOPQRSTUVWY',
211               Z   => 'QE',
212               B   => 'ND',
213            },
214         );
215
216         # Make %convert hash key/value agnostic.
217         foreach my $alphabet ( keys %convert ) {
218            map { $convert{$alphabet}->{ $convert{$alphabet}{$_} } = $_ }
219                keys %{ $convert{$alphabet} };
220         }
221      }
222
223      return $convert{$alphabet}{$letter};
224   }
225
226}
227
228sub _uniq_string {
229   # Takes a list of letters and returns an alphabetically sorted
230   # list with unique elements.
231
232   my @letters = @_;
233   return join '', sort { $a cmp $b } uniq @letters;
234}
235
236{
237   my ( @codon_library, $ct );
238
239   sub _negated_aas_to_codon {
240
241      # Given a string of residues, returns a degenerate codon that will
242      # not be translated into any of them, while maximizing degeneracy
243      # (ie, it tries to also translate into as many residues as possible).
244
245      # This functionality is required for reverse translating profiles
246      # that contain negative patterns: [^X]. This means that the current
247      # position should not contain aminoacid X, but can have any of the
248      # others. The reverse translated nucleotide sequence should
249      # reflect this.
250
251      # Approach: construct a list of all possible codons, incluiding all
252      # degenerate bases. This is an array of 15x15x15 = 3375 elements.
253      # Order them by descendent "degeneracy".
254      # Return the first one whose expansion in 4-lettered codons
255      # doesn't contain a codon that translates into any of the
256      # non-wanted residues.
257
258      # * Since this takes some time, I presorted them and saved them.
259      # Reading them from a file takes a fraction of the time that it taes
260      # to re-sort them every time the application is launched.
261
262      my $aas_to_avoid = shift;
263
264      # Initialize reusable variables if it's the first time the sub
265      # is called.
266      unless (@codon_library) {
267         while (<DATA>) { chomp; push @codon_library, split ' ', $_ }
268      }
269      unless ($ct) { $ct = Bio::Tools::CodonTable->new; }
270
271      # Reverse translate the unwanted aminoacids to unwanted codons.
272      my @unwanted_codons;
273      foreach my $aa ( split '', $aas_to_avoid ) {
274         push @unwanted_codons, $ct->revtranslate($aa);
275      }
276
277      foreach my $degenerate_codon (@codon_library) {
278         my @codons  = _expand_codon($degenerate_codon);
279         my $success = 1;
280
281         foreach my $unwanted (@unwanted_codons) {
282            if ( grep { uc $unwanted eq $_ } @codons ) {
283               $success = 0;
284            }
285         }
286
287         if ($success) { return $degenerate_codon }
288      }
289   }
290
291}
292
2931;
294
295=head1 COPYRIGHT & LICENSE
296
297Copyright 2009 Bruno Vecchi, all rights reserved.
298
299This program is free software; you can redistribute it and/or modify it
300under the same terms as Perl itself.
301
302=cut
303
304__DATA__
305NNN NNB NND NNH NNV NBN NDN NHN NVN BNN DNN HNN VNN NBB NBD NBH NBV NDB NDD
306NDH NDV NHB NHD NHH NHV NVB NVD NVH NVV BNB BND BNH BNV BBN BDN BHN BVN DNB
307DND DNH DNV DBN DDN DHN DVN HNB HND HNH HNV HBN HDN HHN HVN VNB VND VNH VNV
308VBN VDN VHN VVN NNK NNM NNR NNS NNW NNY NKN NMN NRN NSN NWN NYN KNN MNN RNN
309SNN WNN YNN BBB BBD BBH BBV BDB BDD BDH BDV BHB BHD BHH BHV BVB BVD BVH BVV
310DBB DBD DBH DBV DDB DDD DDH DDV DHB DHD DHH DHV DVB DVD DVH DVV HBB HBD HBH
311HBV HDB HDD HDH HDV HHB HHD HHH HHV HVB HVD HVH HVV VBB VBD VBH VBV VDB VDD
312VDH VDV VHB VHD VHH VHV VVB VVD VVH VVV NBK NBM NBR NBS NBW NBY NDK NDM NDR
313NDS NDW NDY NHK NHM NHR NHS NHW NHY NVK NVM NVR NVS NVW NVY NKB NKD NKH NKV
314NMB NMD NMH NMV NRB NRD NRH NRV NSB NSD NSH NSV NWB NWD NWH NWV NYB NYD NYH
315NYV BNK BNM BNR BNS BNW BNY BKN BMN BRN BSN BWN BYN DNK DNM DNR DNS DNW DNY
316DKN DMN DRN DSN DWN DYN HNK HNM HNR HNS HNW HNY HKN HMN HRN HSN HWN HYN VNK
317VNM VNR VNS VNW VNY VKN VMN VRN VSN VWN VYN KNB KND KNH KNV KBN KDN KHN KVN
318MNB MND MNH MNV MBN MDN MHN MVN RNB RND RNH RNV RBN RDN RHN RVN SNB SND SNH
319SNV SBN SDN SHN SVN WNB WND WNH WNV WBN WDN WHN WVN YNB YND YNH YNV YBN YDN
320YHN YVN BBK BBM BBR BBS BBW BBY BDK BDM BDR BDS BDW BDY BHK BHM BHR BHS BHW
321BHY BVK BVM BVR BVS BVW BVY BKB BKD BKH BKV BMB BMD BMH BMV BRB BRD BRH BRV
322BSB BSD BSH BSV BWB BWD BWH BWV BYB BYD BYH BYV DBK DBM DBR DBS DBW DBY DDK
323DDM DDR DDS DDW DDY DHK DHM DHR DHS DHW DHY DVK DVM DVR DVS DVW DVY DKB DKD
324DKH DKV DMB DMD DMH DMV DRB DRD DRH DRV DSB DSD DSH DSV DWB DWD DWH DWV DYB
325DYD DYH DYV HBK HBM HBR HBS HBW HBY HDK HDM HDR HDS HDW HDY HHK HHM HHR HHS
326HHW HHY HVK HVM HVR HVS HVW HVY HKB HKD HKH HKV HMB HMD HMH HMV HRB HRD HRH
327HRV HSB HSD HSH HSV HWB HWD HWH HWV HYB HYD HYH HYV VBK VBM VBR VBS VBW VBY
328VDK VDM VDR VDS VDW VDY VHK VHM VHR VHS VHW VHY VVK VVM VVR VVS VVW VVY VKB
329VKD VKH VKV VMB VMD VMH VMV VRB VRD VRH VRV VSB VSD VSH VSV VWB VWD VWH VWV
330VYB VYD VYH VYV KBB KBD KBH KBV KDB KDD KDH KDV KHB KHD KHH KHV KVB KVD KVH
331KVV MBB MBD MBH MBV MDB MDD MDH MDV MHB MHD MHH MHV MVB MVD MVH MVV RBB RBD
332RBH RBV RDB RDD RDH RDV RHB RHD RHH RHV RVB RVD RVH RVV SBB SBD SBH SBV SDB
333SDD SDH SDV SHB SHD SHH SHV SVB SVD SVH SVV WBB WBD WBH WBV WDB WDD WDH WDV
334WHB WHD WHH WHV WVB WVD WVH WVV YBB YBD YBH YBV YDB YDD YDH YDV YHB YHD YHH
335YHV YVB YVD YVH YVV NNA NNC NNT NNG NKK NKM NKR NKS NKW NKY NMK NMM NMR NMS
336NMW NMY NRK NRM NRR NRS NRW NRY NSK NSM NSR NSS NSW NSY NWK NWM NWR NWS NWW
337NWY NYK NYM NYR NYS NYW NYY NAN NCN NTN NGN KNK KNM KNR KNS KNW KNY KKN KMN
338KRN KSN KWN KYN MNK MNM MNR MNS MNW MNY MKN MMN MRN MSN MWN MYN RNK RNM RNR
339RNS RNW RNY RKN RMN RRN RSN RWN RYN SNK SNM SNR SNS SNW SNY SKN SMN SRN SSN
340SWN SYN WNK WNM WNR WNS WNW WNY WKN WMN WRN WSN WWN WYN YNK YNM YNR YNS YNW
341YNY YKN YMN YRN YSN YWN YYN ANN CNN TNN GNN NBA NBC NBT NBG NDA NDC NDT NDG
342NHA NHC NHT NHG NVA NVC NVT NVG NAB NAD NAH NAV NCB NCD NCH NCV NTB NTD NTH
343NTV NGB NGD NGH NGV BNA BNC BNT BNG BKK BKM BKR BKS BKW BKY BMK BMM BMR BMS
344BMW BMY BRK BRM BRR BRS BRW BRY BSK BSM BSR BSS BSW BSY BWK BWM BWR BWS BWW
345BWY BYK BYM BYR BYS BYW BYY BAN BCN BTN BGN DNA DNC DNT DNG DKK DKM DKR DKS
346DKW DKY DMK DMM DMR DMS DMW DMY DRK DRM DRR DRS DRW DRY DSK DSM DSR DSS DSW
347DSY DWK DWM DWR DWS DWW DWY DYK DYM DYR DYS DYW DYY DAN DCN DTN DGN HNA HNC
348HNT HNG HKK HKM HKR HKS HKW HKY HMK HMM HMR HMS HMW HMY HRK HRM HRR HRS HRW
349HRY HSK HSM HSR HSS HSW HSY HWK HWM HWR HWS HWW HWY HYK HYM HYR HYS HYW HYY
350HAN HCN HTN HGN VNA VNC VNT VNG VKK VKM VKR VKS VKW VKY VMK VMM VMR VMS VMW
351VMY VRK VRM VRR VRS VRW VRY VSK VSM VSR VSS VSW VSY VWK VWM VWR VWS VWW VWY
352VYK VYM VYR VYS VYW VYY VAN VCN VTN VGN KBK KBM KBR KBS KBW KBY KDK KDM KDR
353KDS KDW KDY KHK KHM KHR KHS KHW KHY KVK KVM KVR KVS KVW KVY KKB KKD KKH KKV
354KMB KMD KMH KMV KRB KRD KRH KRV KSB KSD KSH KSV KWB KWD KWH KWV KYB KYD KYH
355KYV MBK MBM MBR MBS MBW MBY MDK MDM MDR MDS MDW MDY MHK MHM MHR MHS MHW MHY
356MVK MVM MVR MVS MVW MVY MKB MKD MKH MKV MMB MMD MMH MMV MRB MRD MRH MRV MSB
357MSD MSH MSV MWB MWD MWH MWV MYB MYD MYH MYV RBK RBM RBR RBS RBW RBY RDK RDM
358RDR RDS RDW RDY RHK RHM RHR RHS RHW RHY RVK RVM RVR RVS RVW RVY RKB RKD RKH
359RKV RMB RMD RMH RMV RRB RRD RRH RRV RSB RSD RSH RSV RWB RWD RWH RWV RYB RYD
360RYH RYV SBK SBM SBR SBS SBW SBY SDK SDM SDR SDS SDW SDY SHK SHM SHR SHS SHW
361SHY SVK SVM SVR SVS SVW SVY SKB SKD SKH SKV SMB SMD SMH SMV SRB SRD SRH SRV
362SSB SSD SSH SSV SWB SWD SWH SWV SYB SYD SYH SYV WBK WBM WBR WBS WBW WBY WDK
363WDM WDR WDS WDW WDY WHK WHM WHR WHS WHW WHY WVK WVM WVR WVS WVW WVY WKB WKD
364WKH WKV WMB WMD WMH WMV WRB WRD WRH WRV WSB WSD WSH WSV WWB WWD WWH WWV WYB
365WYD WYH WYV YBK YBM YBR YBS YBW YBY YDK YDM YDR YDS YDW YDY YHK YHM YHR YHS
366YHW YHY YVK YVM YVR YVS YVW YVY YKB YKD YKH YKV YMB YMD YMH YMV YRB YRD YRH
367YRV YSB YSD YSH YSV YWB YWD YWH YWV YYB YYD YYH YYV ANB AND ANH ANV ABN ADN
368AHN AVN CNB CND CNH CNV CBN CDN CHN CVN TNB TND TNH TNV TBN TDN THN TVN GNB
369GND GNH GNV GBN GDN GHN GVN BBA BBC BBT BBG BDA BDC BDT BDG BHA BHC BHT BHG
370BVA BVC BVT BVG BAB BAD BAH BAV BCB BCD BCH BCV BTB BTD BTH BTV BGB BGD BGH
371BGV DBA DBC DBT DBG DDA DDC DDT DDG DHA DHC DHT DHG DVA DVC DVT DVG DAB DAD
372DAH DAV DCB DCD DCH DCV DTB DTD DTH DTV DGB DGD DGH DGV HBA HBC HBT HBG HDA
373HDC HDT HDG HHA HHC HHT HHG HVA HVC HVT HVG HAB HAD HAH HAV HCB HCD HCH HCV
374HTB HTD HTH HTV HGB HGD HGH HGV VBA VBC VBT VBG VDA VDC VDT VDG VHA VHC VHT
375VHG VVA VVC VVT VVG VAB VAD VAH VAV VCB VCD VCH VCV VTB VTD VTH VTV VGB VGD
376VGH VGV ABB ABD ABH ABV ADB ADD ADH ADV AHB AHD AHH AHV AVB AVD AVH AVV CBB
377CBD CBH CBV CDB CDD CDH CDV CHB CHD CHH CHV CVB CVD CVH CVV TBB TBD TBH TBV
378TDB TDD TDH TDV THB THD THH THV TVB TVD TVH TVV GBB GBD GBH GBV GDB GDD GDH
379GDV GHB GHD GHH GHV GVB GVD GVH GVV NKA NKC NKT NKG NMA NMC NMT NMG NRA NRC
380NRT NRG NSA NSC NST NSG NWA NWC NWT NWG NYA NYC NYT NYG NAK NAM NAR NAS NAW
381NAY NCK NCM NCR NCS NCW NCY NTK NTM NTR NTS NTW NTY NGK NGM NGR NGS NGW NGY
382KNA KNC KNT KNG KKK KKM KKR KKS KKW KKY KMK KMM KMR KMS KMW KMY KRK KRM KRR
383KRS KRW KRY KSK KSM KSR KSS KSW KSY KWK KWM KWR KWS KWW KWY KYK KYM KYR KYS
384KYW KYY KAN KCN KTN KGN MNA MNC MNT MNG MKK MKM MKR MKS MKW MKY MMK MMM MMR
385MMS MMW MMY MRK MRM MRR MRS MRW MRY MSK MSM MSR MSS MSW MSY MWK MWM MWR MWS
386MWW MWY MYK MYM MYR MYS MYW MYY MAN MCN MTN MGN RNA RNC RNT RNG RKK RKM RKR
387RKS RKW RKY RMK RMM RMR RMS RMW RMY RRK RRM RRR RRS RRW RRY RSK RSM RSR RSS
388RSW RSY RWK RWM RWR RWS RWW RWY RYK RYM RYR RYS RYW RYY RAN RCN RTN RGN SNA
389SNC SNT SNG SKK SKM SKR SKS SKW SKY SMK SMM SMR SMS SMW SMY SRK SRM SRR SRS
390SRW SRY SSK SSM SSR SSS SSW SSY SWK SWM SWR SWS SWW SWY SYK SYM SYR SYS SYW
391SYY SAN SCN STN SGN WNA WNC WNT WNG WKK WKM WKR WKS WKW WKY WMK WMM WMR WMS
392WMW WMY WRK WRM WRR WRS WRW WRY WSK WSM WSR WSS WSW WSY WWK WWM WWR WWS WWW
393WWY WYK WYM WYR WYS WYW WYY WAN WCN WTN WGN YNA YNC YNT YNG YKK YKM YKR YKS
394YKW YKY YMK YMM YMR YMS YMW YMY YRK YRM YRR YRS YRW YRY YSK YSM YSR YSS YSW
395YSY YWK YWM YWR YWS YWW YWY YYK YYM YYR YYS YYW YYY YAN YCN YTN YGN ANK ANM
396ANR ANS ANW ANY AKN AMN ARN ASN AWN AYN CNK CNM CNR CNS CNW CNY CKN CMN CRN
397CSN CWN CYN TNK TNM TNR TNS TNW TNY TKN TMN TRN TSN TWN TYN GNK GNM GNR GNS
398GNW GNY GKN GMN GRN GSN GWN GYN BKA BKC BKT BKG BMA BMC BMT BMG BRA BRC BRT
399BRG BSA BSC BST BSG BWA BWC BWT BWG BYA BYC BYT BYG BAK BAM BAR BAS BAW BAY
400BCK BCM BCR BCS BCW BCY BTK BTM BTR BTS BTW BTY BGK BGM BGR BGS BGW BGY DKA
401DKC DKT DKG DMA DMC DMT DMG DRA DRC DRT DRG DSA DSC DST DSG DWA DWC DWT DWG
402DYA DYC DYT DYG DAK DAM DAR DAS DAW DAY DCK DCM DCR DCS DCW DCY DTK DTM DTR
403DTS DTW DTY DGK DGM DGR DGS DGW DGY HKA HKC HKT HKG HMA HMC HMT HMG HRA HRC
404HRT HRG HSA HSC HST HSG HWA HWC HWT HWG HYA HYC HYT HYG HAK HAM HAR HAS HAW
405HAY HCK HCM HCR HCS HCW HCY HTK HTM HTR HTS HTW HTY HGK HGM HGR HGS HGW HGY
406VKA VKC VKT VKG VMA VMC VMT VMG VRA VRC VRT VRG VSA VSC VST VSG VWA VWC VWT
407VWG VYA VYC VYT VYG VAK VAM VAR VAS VAW VAY VCK VCM VCR VCS VCW VCY VTK VTM
408VTR VTS VTW VTY VGK VGM VGR VGS VGW VGY KBA KBC KBT KBG KDA KDC KDT KDG KHA
409KHC KHT KHG KVA KVC KVT KVG KAB KAD KAH KAV KCB KCD KCH KCV KTB KTD KTH KTV
410KGB KGD KGH KGV MBA MBC MBT MBG MDA MDC MDT MDG MHA MHC MHT MHG MVA MVC MVT
411MVG MAB MAD MAH MAV MCB MCD MCH MCV MTB MTD MTH MTV MGB MGD MGH MGV RBA RBC
412RBT RBG RDA RDC RDT RDG RHA RHC RHT RHG RVA RVC RVT RVG RAB RAD RAH RAV RCB
413RCD RCH RCV RTB RTD RTH RTV RGB RGD RGH RGV SBA SBC SBT SBG SDA SDC SDT SDG
414SHA SHC SHT SHG SVA SVC SVT SVG SAB SAD SAH SAV SCB SCD SCH SCV STB STD STH
415STV SGB SGD SGH SGV WBA WBC WBT WBG WDA WDC WDT WDG WHA WHC WHT WHG WVA WVC
416WVT WVG WAB WAD WAH WAV WCB WCD WCH WCV WTB WTD WTH WTV WGB WGD WGH WGV YBA
417YBC YBT YBG YDA YDC YDT YDG YHA YHC YHT YHG YVA YVC YVT YVG YAB YAD YAH YAV
418YCB YCD YCH YCV YTB YTD YTH YTV YGB YGD YGH YGV ABK ABM ABR ABS ABW ABY ADK
419ADM ADR ADS ADW ADY AHK AHM AHR AHS AHW AHY AVK AVM AVR AVS AVW AVY AKB AKD
420AKH AKV AMB AMD AMH AMV ARB ARD ARH ARV ASB ASD ASH ASV AWB AWD AWH AWV AYB
421AYD AYH AYV CBK CBM CBR CBS CBW CBY CDK CDM CDR CDS CDW CDY CHK CHM CHR CHS
422CHW CHY CVK CVM CVR CVS CVW CVY CKB CKD CKH CKV CMB CMD CMH CMV CRB CRD CRH
423CRV CSB CSD CSH CSV CWB CWD CWH CWV CYB CYD CYH CYV TBK TBM TBR TBS TBW TBY
424TDK TDM TDR TDS TDW TDY THK THM THR THS THW THY TVK TVM TVR TVS TVW TVY TKB
425TKD TKH TKV TMB TMD TMH TMV TRB TRD TRH TRV TSB TSD TSH TSV TWB TWD TWH TWV
426TYB TYD TYH TYV GBK GBM GBR GBS GBW GBY GDK GDM GDR GDS GDW GDY GHK GHM GHR
427GHS GHW GHY GVK GVM GVR GVS GVW GVY GKB GKD GKH GKV GMB GMD GMH GMV GRB GRD
428GRH GRV GSB GSD GSH GSV GWB GWD GWH GWV GYB GYD GYH GYV NAA NAC NAT NAG NCA
429NCC NCT NCG NTA NTC NTT NTG NGA NGC NGT NGG KKA KKC KKT KKG KMA KMC KMT KMG
430KRA KRC KRT KRG KSA KSC KST KSG KWA KWC KWT KWG KYA KYC KYT KYG KAK KAM KAR
431KAS KAW KAY KCK KCM KCR KCS KCW KCY KTK KTM KTR KTS KTW KTY KGK KGM KGR KGS
432KGW KGY MKA MKC MKT MKG MMA MMC MMT MMG MRA MRC MRT MRG MSA MSC MST MSG MWA
433MWC MWT MWG MYA MYC MYT MYG MAK MAM MAR MAS MAW MAY MCK MCM MCR MCS MCW MCY
434MTK MTM MTR MTS MTW MTY MGK MGM MGR MGS MGW MGY RKA RKC RKT RKG RMA RMC RMT
435RMG RRA RRC RRT RRG RSA RSC RST RSG RWA RWC RWT RWG RYA RYC RYT RYG RAK RAM
436RAR RAS RAW RAY RCK RCM RCR RCS RCW RCY RTK RTM RTR RTS RTW RTY RGK RGM RGR
437RGS RGW RGY SKA SKC SKT SKG SMA SMC SMT SMG SRA SRC SRT SRG SSA SSC SST SSG
438SWA SWC SWT SWG SYA SYC SYT SYG SAK SAM SAR SAS SAW SAY SCK SCM SCR SCS SCW
439SCY STK STM STR STS STW STY SGK SGM SGR SGS SGW SGY WKA WKC WKT WKG WMA WMC
440WMT WMG WRA WRC WRT WRG WSA WSC WST WSG WWA WWC WWT WWG WYA WYC WYT WYG WAK
441WAM WAR WAS WAW WAY WCK WCM WCR WCS WCW WCY WTK WTM WTR WTS WTW WTY WGK WGM
442WGR WGS WGW WGY YKA YKC YKT YKG YMA YMC YMT YMG YRA YRC YRT YRG YSA YSC YST
443YSG YWA YWC YWT YWG YYA YYC YYT YYG YAK YAM YAR YAS YAW YAY YCK YCM YCR YCS
444YCW YCY YTK YTM YTR YTS YTW YTY YGK YGM YGR YGS YGW YGY ANA ANC ANT ANG AKK
445AKM AKR AKS AKW AKY AMK AMM AMR AMS AMW AMY ARK ARM ARR ARS ARW ARY ASK ASM
446ASR ASS ASW ASY AWK AWM AWR AWS AWW AWY AYK AYM AYR AYS AYW AYY AAN ACN ATN
447AGN CNA CNC CNT CNG CKK CKM CKR CKS CKW CKY CMK CMM CMR CMS CMW CMY CRK CRM
448CRR CRS CRW CRY CSK CSM CSR CSS CSW CSY CWK CWM CWR CWS CWW CWY CYK CYM CYR
449CYS CYW CYY CAN CCN CTN CGN TNA TNC TNT TNG TKK TKM TKR TKS TKW TKY TMK TMM
450TMR TMS TMW TMY TRK TRM TRR TRS TRW TRY TSK TSM TSR TSS TSW TSY TWK TWM TWR
451TWS TWW TWY TYK TYM TYR TYS TYW TYY TAN TCN TTN TGN GNA GNC GNT GNG GKK GKM
452GKR GKS GKW GKY GMK GMM GMR GMS GMW GMY GRK GRM GRR GRS GRW GRY GSK GSM GSR
453GSS GSW GSY GWK GWM GWR GWS GWW GWY GYK GYM GYR GYS GYW GYY GAN GCN GTN GGN
454BAA BAC BAT BAG BCA BCC BCT BCG BTA BTC BTT BTG BGA BGC BGT BGG DAA DAC DAT
455DAG DCA DCC DCT DCG DTA DTC DTT DTG DGA DGC DGT DGG HAA HAC HAT HAG HCA HCC
456HCT HCG HTA HTC HTT HTG HGA HGC HGT HGG VAA VAC VAT VAG VCA VCC VCT VCG VTA
457VTC VTT VTG VGA VGC VGT VGG ABA ABC ABT ABG ADA ADC ADT ADG AHA AHC AHT AHG
458AVA AVC AVT AVG AAB AAD AAH AAV ACB ACD ACH ACV ATB ATD ATH ATV AGB AGD AGH
459AGV CBA CBC CBT CBG CDA CDC CDT CDG CHA CHC CHT CHG CVA CVC CVT CVG CAB CAD
460CAH CAV CCB CCD CCH CCV CTB CTD CTH CTV CGB CGD CGH CGV TBA TBC TBT TBG TDA
461TDC TDT TDG THA THC THT THG TVA TVC TVT TVG TAB TAD TAH TAV TCB TCD TCH TCV
462TTB TTD TTH TTV TGB TGD TGH TGV GBA GBC GBT GBG GDA GDC GDT GDG GHA GHC GHT
463GHG GVA GVC GVT GVG GAB GAD GAH GAV GCB GCD GCH GCV GTB GTD GTH GTV GGB GGD
464GGH GGV KAA KAC KAT KAG KCA KCC KCT KCG KTA KTC KTT KTG KGA KGC KGT KGG MAA
465MAC MAT MAG MCA MCC MCT MCG MTA MTC MTT MTG MGA MGC MGT MGG RAA RAC RAT RAG
466RCA RCC RCT RCG RTA RTC RTT RTG RGA RGC RGT RGG SAA SAC SAT SAG SCA SCC SCT
467SCG STA STC STT STG SGA SGC SGT SGG WAA WAC WAT WAG WCA WCC WCT WCG WTA WTC
468WTT WTG WGA WGC WGT WGG YAA YAC YAT YAG YCA YCC YCT YCG YTA YTC YTT YTG YGA
469YGC YGT YGG AKA AKC AKT AKG AMA AMC AMT AMG ARA ARC ART ARG ASA ASC AST ASG
470AWA AWC AWT AWG AYA AYC AYT AYG AAK AAM AAR AAS AAW AAY ACK ACM ACR ACS ACW
471ACY ATK ATM ATR ATS ATW ATY AGK AGM AGR AGS AGW AGY CKA CKC CKT CKG CMA CMC
472CMT CMG CRA CRC CRT CRG CSA CSC CST CSG CWA CWC CWT CWG CYA CYC CYT CYG CAK
473CAM CAR CAS CAW CAY CCK CCM CCR CCS CCW CCY CTK CTM CTR CTS CTW CTY CGK CGM
474CGR CGS CGW CGY TKA TKC TKT TKG TMA TMC TMT TMG TRA TRC TRT TRG TSA TSC TST
475TSG TWA TWC TWT TWG TYA TYC TYT TYG TAK TAM TAR TAS TAW TAY TCK TCM TCR TCS
476TCW TCY TTK TTM TTR TTS TTW TTY TGK TGM TGR TGS TGW TGY GKA GKC GKT GKG GMA
477GMC GMT GMG GRA GRC GRT GRG GSA GSC GST GSG GWA GWC GWT GWG GYA GYC GYT GYG
478GAK GAM GAR GAS GAW GAY GCK GCM GCR GCS GCW GCY GTK GTM GTR GTS GTW GTY GGK
479GGM GGR GGS GGW GGY AAA AAC AAT AAG ACA ACC ACT ACG ATA ATC ATT ATG AGA AGC
480AGT AGG CAA CAC CAT CAG CCA CCC CCT CCG CTA CTC CTT CTG CGA CGC CGT CGG TAA
481TAC TAT TAG TCA TCC TCT TCG TTA TTC TTT TTG TGA TGC TGT TGG GAA GAC GAT GAG
482GCA GCC GCT GCG GTA GTC GTT GTG GGA GGC GGT GGG
483