-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathtrevolver.pl
executable file
·2639 lines (2056 loc) · 101 KB
/
trevolver.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#! /usr/bin/perl
#########################################################################################
# Perl script to simulate sequence evolution on a BIFURCATING TREE provided in Newick
# format with a user-provided TRINUCLEOTIDE (64 x 4) rate matrix, such as that described
# in SLiM. This allows non-reversible context-dependent evolution with back mutation.
# OUTPUTS: mutation data, VCF file
#########################################################################################
# EXAMPLES
#########################################################################################
# [FORMAT] trevolver.pl --tree=<newick>.txt --seed_sequence=<seed>.fasta --rate_matrix=<64x4>.txt --branch_unit=<#> --random_seed=<#>
#########################################################################################
# [EXAMPLE 1] trevolver.pl --tree=../EXAMPLE_INPUT/tree_6taxa.txt --seed_sequence=../EXAMPLE_INPUT/seed_sequence.fa --rate_matrix=../EXAMPLE_INPUT/mutation_CpGx20.txt --vcf_output=example1.vcf --branch_unit=10000 > example1.txt
#########################################################################################
# [EXAMPLE 2] trevolver.pl --tree=../EXAMPLE_INPUT/tree_6taxa.txt --seed_sequence=../EXAMPLE_INPUT/seed_sequence.fa --rate_matrix=../EXAMPLE_INPUT/mutation_CpGx20.txt --vcf_output=example2.vcf --branch_unit=10000 --burn_in=1000 > example2.txt
#########################################################################################
# [EXAMPLE 3] trevolver.pl --tree=../EXAMPLE_INPUT/tree_6taxa.txt --seed_sequence=../EXAMPLE_INPUT/seed_sequence.fa --rate_matrix=../EXAMPLE_INPUT/mutation_CpGx20.txt --branch_unit=144740 --track_mutations --tracked_motif=CG --vcf_output=example3.vcf > example3.txt
#########################################################################################
# [EXAMPLE 4] trevolver.pl --tree=../EXAMPLE_INPUT/tree_10taxa.txt --seed_sequence=../EXAMPLE_INPUT/seed_sequence.fa --rate_matrix=../EXAMPLE_INPUT/mutation_CpGx20.txt --branch_unit=144740 --track_mutations --tracked_motif=CG --vcf_output=example4.vcf --outgroups=2 > example4.txt
#########################################################################################
# [EXAMPLE 5] trevolver.pl --tree=../EXAMPLE_INPUT/tree_1taxon.txt --seed_sequence=../EXAMPLE_INPUT/seed_sequence.fa --rate_matrix=../EXAMPLE_INPUT/mutation_equal.txt --vcf_output=example5.vcf --branch_unit=1 > example5.txt
#########################################################################################
# [EXAMPLE 6] trevolver.pl --tree=../EXAMPLE_INPUT/tree_7taxa.txt --seed_sequence=../EXAMPLE_INPUT/seed_sequence.fa --rate_matrix=../EXAMPLE_INPUT/mutation_equal.txt --branch_unit=144740 --random_seed=123456789 --tracked_motif=CG --track_mutations --vcf_output=example6.vcf --outgroups=2 --burn_in=500 --suppress_seed_seq --suppress_consensus_seq --verbose > example6.txt
#########################################################################################
# [EXAMPLE 7] trevolver.pl --tree=../EXAMPLE_INPUT/tree_7taxa.txt --seed_sequence=../EXAMPLE_INPUT/seed_sequence.fa --rate_matrix=../EXAMPLE_INPUT/mutation_CpGx20.txt --branch_unit=1447
#########################################################################################
#########################################################################################
# Copyright (C) 2019 Chase W. Nelson
# DATE CREATED: June 2019
# AUTHOR: Chase W. Nelson
# CONTACT1: cnelson@amnh.org
# AFFILIATION: Sackler Institute for Comparative Genomics, American Museum of Natural
# History, New York, NY 10024, USA
# ACKNOWLEDGMENTS: written by C.W.N. with support from a Gerstner Scholars Fellowship from
# the Gerstner Family Foundation at the American Museum of Natural History, New York.
#########################################################################################
use strict;
use List::Util qw(max sum);
use Getopt::Long;
STDOUT->autoflush(1);
# Get the time
my $time1 = time;
my $local_time1 = localtime;
my @commands = @ARGV;
#########################################################################################
# INITIALIZE INPUT VARIABLES
my $tree; # file containing bifurcating evolutionary tree with branch lengths
my $seed_sequence; # file containing starting (seed) sequence at tree root, to be evolved
my $rate_matrix; # file containing 64 x 4 tab-delimited rate matrix in alphabetical order. First row values for: AAA>AAA\tAAA>ACA\tAAA>AGA\tAAA>ATA\n
my $branch_unit; # branch lengths will be multiplied by this value and rounded up to the nearest integer to determine number of generations
my $random_seed; # integer with which to seed the random number generator
my $tracked_motif;
my $track_mutations;
my $vcf_output;
my $excluded_taxa;
my $outgroups;
my $burn_in;
my $suppress_input_seq;
my $suppress_seed_seq;
my $suppress_MRCA_seq;
my $suppress_consensus_seq;
my $suppress_MUTATION;
my $verbose;
# Get user input, if given. If a Boolean argument is passed, its value is 1; else undef
GetOptions( "tree=s" => \$tree,
"seed_sequence=s" => \$seed_sequence,
"rate_matrix=s" => \$rate_matrix,
"branch_unit=f" => \$branch_unit,
"random_seed=i" => \$random_seed,
"tracked_motif=s" => \$tracked_motif,
"track_mutations" => \$track_mutations,
"vcf_output=s" => \$vcf_output,
"excluded_taxa=s" => \$excluded_taxa,
"outgroups=i" => \$outgroups,
"burn_in=i" => \$burn_in,
"suppress_input_seq" => \$suppress_input_seq,
"suppress_seed_seq" => \$suppress_seed_seq,
"suppress_MRCA_seq" => \$suppress_MRCA_seq,
"suppress_consensus_seq" => \$suppress_consensus_seq,
"suppress_MUTATION" => \$suppress_MUTATION,
"verbose" => \$verbose
)
or print_usage_message("### WARNING: Error in command line arguments (option misspelled?). trevolver terminated.");
#print "\nvcf_output=$vcf_output\n"; # the value of a called flag is 1
unless(-f "$tree") {
my $specific_warning = "### WARNING: A valid --tree option must be provided.";
print_usage_message($specific_warning);
}
unless(-f "$seed_sequence") {
my $specific_warning = "### WARNING: A valid --seed_sequence option must be provided.";
print_usage_message($specific_warning);
}
unless(-f "$rate_matrix") {
my $specific_warning = "### WARNING: A valid --rate_matrix option must be provided.";
print_usage_message($specific_warning);
}
unless($branch_unit =~ /\d/) {
my $specific_warning = "### WARNING: A valid --branch_unit option must be provided.";
print_usage_message($specific_warning);
}
if (-f "$vcf_output" || $vcf_output =~ /^\-/) {
my $specific_warning = "### WARNING: A valid --vcf_output file name must be provided (or already exists).";
print_usage_message($specific_warning);
}
#if ($excluded_taxa && $outgroups) {
# my $specific_warning = "### WARNING: The --excluded_taxa and --outgroups options are mutually exclusive; they cannot both be called.";
# print_usage_message($specific_warning);
#}
my $working_directory = `pwd`;
chomp($working_directory);
#print "\nworking_directory=$working_directory\n"; # does NOT include a trailing forward slash, but does end in a newline
##########################################################################################
# Extract tree file prefix
my $file_prefix;
if($tree =~/\/*([^\/]+)\..+/) {
$file_prefix = $1;
} else {
$file_prefix = 'trevolver_input';
}
unless ($vcf_output =~ /\w/) {
$vcf_output = $file_prefix . ".vcf";
}
##########################################################################################
# Store the tree(s)
open(IN_TREE, "$tree") or die "Could not open file $tree\n";
my $tree = '';
# Store first tree in file
while(<IN_TREE>) {
chomp($_);
my $line = $_;
if($line =~ /^\(/) { # line starts with an opening parentheses
if($line =~ /\);$/) { # line ends with a closing parentheses and semicolon
$tree = $line;
last;
}
}
}
close IN_TREE;
if($tree eq '') {
my $specific_warning = "### WARNING: NO TREE IN TREE FILE. Must begin with '(' and end with ');'.";
print_usage_message($specific_warning);
}
# Trim end of tree if ';' or whitespace
#print "\nTREE:\n$tree\n\n";
while(substr($tree, -1) =~ /[\s\;]/) {
chop($tree);
}
#print "\nPROCESSED TREE:\n$tree\n\n";
if($tree =~ /(\,[a-zA-Z0-9\.\-\|\:\']+\,)/) {
my $specific_warning = "### WARNING: TREE MUST BE STRICTLY BIFURCATING BUT CONTAINS A POLYTOMY: $1";
print_usage_message($specific_warning);
}
if($tree =~ /(\(\,[^\(]*\,\()/) {
my $specific_warning = "### WARNING: TREE MUST BE STRICTLY BIFURCATING BUT CONTAINS A POLYTOMY: $1";
print_usage_message($specific_warning);
}
if($tree =~ /(\)\d+)/) {
my $specific_warning = "### WARNING: CURRENTLY, SUPPORT VALUES ARE NOT ALLOWED BUT ARE PRESENT: $1";
print_usage_message($specific_warning);
}
if($tree =~ /(\)\[)/) {
my $specific_warning = "### WARNING: CURRENTLY, SUPPORT VALUES ARE NOT ALLOWED BUT ARE PRESENT: $1";
print_usage_message($specific_warning);
}
if($tree =~ /(\],)/) {
my $specific_warning = "### WARNING: CURRENTLY, SUPPORT VALUES ARE NOT ALLOWED BUT ARE PRESENT: $1";
print_usage_message($specific_warning);
}
my $tree_opening_paren_count = ($tree =~ s/\(/\(/g);
my $tree_closing_paren_count = ($tree =~ s/\)/\)/g);
unless($tree_opening_paren_count > 0 && $tree_opening_paren_count == $tree_closing_paren_count) {
my $specific_warning = "### WARNING: TREE MUST CONTAIN EQUAL NUMBERS OF OPENING (now $tree_opening_paren_count\) AND CLOSING " .
"(now $tree_closing_paren_count\) PARENTHESES.";
print_usage_message($specific_warning);
}
##########################################################################################
# Read in the seed sequence from the fasta file
my $seed_seq = '';
my $seq_num = 0;
open(IN_FASTA, "$seed_sequence") or die "Could not open file $seed_sequence\n";
if($verbose) {
print "\n################################################################################";
print "\nRecording seed sequence data from $seed_sequence...\n";
}
my $fasta_header = '';
while(<IN_FASTA>) {
chomp;
if(/>([\S]+)\s*/) {
$fasta_header = $1;
if($seq_num == 0) {
$seq_num ++;
} else {
last;
}
} else {
$seed_seq .= $_;
}
}
close IN_FASTA;
$seed_seq = uc($seed_seq);
$seed_seq =~ tr/U/T/;
unless($seed_seq =~ /[ACGT]/ && length($seed_seq) >= 3) {
my $specific_warning = "### WARNING: Sequence does not contain more than two nucleotides (A, C, G, T).";
print_usage_message($specific_warning);
}
my $seed_seq_length = length($seed_seq);
##########################################################################################
# Read in the rate matrix
my %rate_matrix;
my @ordered_trinucleotides = qw/AAA AAC AAG AAT
ACA ACC ACG ACT
AGA AGC AGG AGT
ATA ATC ATG ATT
CAA CAC CAG CAT
CCA CCC CCG CCT
CGA CGC CGG CGT
CTA CTC CTG CTT
GAA GAC GAG GAT
GCA GCC GCG GCT
GGA GGC GGG GGT
GTA GTC GTG GTT
TAA TAC TAG TAT
TCA TCC TCG TCT
TGA TGC TGG TGT
TTA TTC TTG TTT/;
# ^ each of those corresponds to ONE ROW of the rate matrix
open(IN_RATE_MATRIX, "$rate_matrix") or die "Could not open file $rate_matrix\n";
if ($verbose) {
print "\n################################################################################";
print "\nRecording rate matrix from $rate_matrix...\n";
}
my $row_index = 0;
my $max_whitespaces = 0;
while(<IN_RATE_MATRIX>) {
chomp;
my $line = $_;
my $num_whitespaces = ($line =~ s/(\s+)/$1/g);
if($num_whitespaces > $max_whitespaces) { $max_whitespaces = $num_whitespaces }
if (/([0-9\.eE\-]+)\s+([0-9\.eE\-]+)\s+([0-9\.eE\-]+)\s+([0-9\.eE\-]+)$/) { # in case there's a header or a column of names in front
$rate_matrix{$ordered_trinucleotides[$row_index]}->{'A'} = $1;
$rate_matrix{$ordered_trinucleotides[$row_index]}->{'C'} = $2;
$rate_matrix{$ordered_trinucleotides[$row_index]}->{'G'} = $3;
$rate_matrix{$ordered_trinucleotides[$row_index]}->{'T'} = $4;
$row_index++;
}
}
close IN_RATE_MATRIX;
unless($row_index == 64 || $max_whitespaces <= 5) { # i.e., one more than the last real index
my $specific_warning = "### WARNING: There must be 64 rows X 4 columns of data in the rate matrix.";
print_usage_message($specific_warning);
}
if ($verbose) { print "\n" }
print "################################################################################".
"\n## ##".
"\n## Evolution On Tree Using Custom Rates Initiated! ##".
"\n## ##".
"\n################################################################################\n";
print "\nAnalysis initiated at local time $local_time1\n";
print "\nCOMMAND: trevolver.pl @commands\n";
##########################################################################################
# Generate or assign random seed value
if($random_seed) {
print "\nRANDOM_SEED: $random_seed\n";
srand($random_seed);
} else {
$random_seed = srand(time ^ $$ ^ unpack "%32L*", `ps wwaxl | gzip`); # (Programming Perl, p. 955)
print "\nRANDOM_SEED: $random_seed\n";
}
##########################################################################################
# Read in the excluded taxa names
my %excluded_taxa_names;
if ($excluded_taxa) {
if (-f "$excluded_taxa") {
open(IN_EXCLUDED_TAXA, "$excluded_taxa");
if($verbose) {
print "\n################################################################################";
print "\nRecording excluded taxa from $excluded_taxa...\n";
}
while(<IN_EXCLUDED_TAXA>) {
chomp;
my $line = $_;
if($line =~ /\w/) {
my @this_line_taxa = split(/\,\s*/, $line);
print "\nEXCLUDED TAXA NAMES: ";
my $excluded_taxa_line = '';
foreach (@this_line_taxa) {
$excluded_taxa_names{$_} = 1;
$excluded_taxa_line .= "$_\,";
}
chop($excluded_taxa_line);
print "$excluded_taxa_line\n";
}
}
close IN_EXCLUDED_TAXA;
} else {
print "\n### WARNING: could not open file $excluded_taxa\. Excluding no taxa.\n";
}
}
##########################################################################################
# STORE THE TREE AS A MULTIDMINENSIONAL HASH
if ($verbose) {
print "\n################################################################################\n";
print "Recursively trevolving sequences from the root...\n";
}
#my %tree;
print "\nTREE: $tree\n";
##########################################################################################
# IDENTIFY AND CHARACTERIZE OUTGROUPS
##########################################################################################
my @outgroup_data; # [0] generation MRCA [1-n] outgroup names
# Obtain OUTGROUP NAMES and the GENERATION in which the MRCA of the ingroup lived.
if ($outgroups) {
if ($verbose) { print "\n### OUTGROUP IDENTIFICATION COMMENCING...\n" }
# PASS: tree, generations elapsed, curr_outgroup_count, outgroup_names
@outgroup_data = determine_outgroup_data($tree, 0, 0, '');
# RETURNS: subtree with MRCA root; generation of MRCA; outgroups 1-n
}
my $MRCA_subtree;
my $MRCA_generation;
if (@outgroup_data) {
$MRCA_subtree = shift(@outgroup_data);
$MRCA_generation = shift(@outgroup_data);
print "\nMRCA_GENERATION: $MRCA_generation\n";
print "\nMRCA_SUBTREE: $MRCA_subtree\n";
print "\nOUTGROUPS: @outgroup_data\n";
} else {
undef($outgroups);
}
#@outgroup_data now contains only outgroup names
if ($outgroups) {
foreach (@outgroup_data) {
$excluded_taxa_names{$_} = 1;
}
}
##########################################################################################
##########################################################################################
##########################################################################################
# BURN-IN
##########################################################################################
my $num_burn_in_mutations = 0;
my $input_seq = '';
if ($burn_in) {
$input_seq = $seed_seq;
$seed_seq = burn_in($seed_seq, $burn_in);
if ($verbose) { print "BURN-IN INVOLVED $num_burn_in_mutations MUTATIONS\n" }
}
if ($input_seq ne '') {
unless($suppress_input_seq) { print "\nINPT_SEQUENCE: $input_seq\n" }
}
unless($suppress_seed_seq) { print "\nSEED_SEQUENCE: $seed_seq\n" }
##########################################################################################
##########################################################################################
##########################################################################################
# THE SIMULATION: recursive evolution approach using the subroutine evolve_branch()
##########################################################################################
my $num_mutations = 0;
my $total_branch_length = 0;
my $root_to_tip_length = 0;
my %taxa_histories;
my %generational_histories;
my $node_id = 0;
my %mutated_sites;
my %MRCA_mutation_history;
my $MRCA_seq;
my $MRCA_node_id;
if ($verbose) { print "\n###EVOLUTION ON TREE COMMENCING...\n" }
evolve_branch($tree, 0, 0, 'n0=root,');
##########################################################################################
##########################################################################################
# Output consensus and MRCA information
if ($outgroups) {
print "\nMRCA_NODE_ID: $MRCA_node_id\n";
unless($suppress_MRCA_seq) { print "\nMRCA_SEQUENCE: $MRCA_seq\n" }
}
##########################################################################################
##########################################################################################
### VCF output
##########################################################################################
##########################################################################################
if ($vcf_output =~ /\w+/) {
chomp($vcf_output);
my (undef, undef, undef, $day, $month, $year) = localtime;
$year = $year + 1900;
$month += 1;
if (length($month) == 1) { $month = "0$month" }
if (length($day) == 1) { $day = "0$day" }
my $today = "$year$month$day";
if ($vcf_output =~ /\//) { # a path was provided
my $vcf_output_dir = $vcf_output;
$vcf_output_dir =~ s/\/[^\/]+$//;
if (-d "$vcf_output_dir") {
if (-f "$vcf_output") { # file already exist?
my $new_vcf_output = "$working_directory\/$file_prefix\_$random_seed\.vcf";
print "\nVCF_OUTPUT_FILE: SPECIFIED FILE ALREADY EXISTS, NEW FILE NAME: $new_vcf_output.\n";
$vcf_output = $new_vcf_output;
} else { # else we're good to go
print "\nVCF_OUTPUT_FILE: $vcf_output.\n";
}
} else {
my $new_vcf_output = "$working_directory\/$file_prefix\_$random_seed\.vcf";
print "\nVCF_OUTPUT_FILE: NON-EXISTENT DIRECTORY SPECIFIED, NEW FILE NAME: $new_vcf_output.\n";
$vcf_output = $new_vcf_output;
}
} else {
print "\nVCF_OUTPUT_FILE: $working_directory\/$vcf_output.\n";
$vcf_output = "$working_directory\/$vcf_output";
}
# Determine site frequency data
my %site_to_alleles; # made only for the INGROUP
my %site_to_outgroups; # made only for the OUTGROUP(S)
my $num_taxa = 0;
my $num_outgroups = 0;
# KEYS of %mutated_sites
foreach my $mutated_site (sort {$a <=> $b} keys %mutated_sites) {
my $AA = substr($seed_seq, $mutated_site - 1, 1);
# Store history
my %prev_state_1;
my %prev_state_2;
my %prev_change;
foreach my $taxon (sort {$a <=> $b} keys %taxa_histories) {
# OUTGROUP(S), if any
if ($excluded_taxa_names{$taxon}) {
if ($taxa_histories{$taxon}->{$mutated_site}) { # this taxon HAS the mutated site
my $mutation_history = $taxa_histories{$taxon}->{$mutated_site};
#print "mutation_history=$mutation_history\n";
my @mutation_history_events = split(/,/, $mutation_history);
my $extant_nt = substr($mutation_history, -1);
#print "extant_nt=$extant_nt\n";
# Store nucleotide
$site_to_outgroups{$mutated_site}->{$extant_nt}++;
foreach my $event (@mutation_history_events) { # these are ordered, but won't matter with new approach
if ($event =~ /(\d+)\-\w\>\w/) {
#91404-A>G
#868627-G>A
my $generation = $1;
$site_to_outgroups{$mutated_site}->{history}->{$generation}->{$event}++;
}
}
} else { # this taxon does NOT have the mutated site, add the ancestral (seed)
$site_to_outgroups{$mutated_site}->{$AA}++;
}
# INGROUP (or, if no outgroups, everything)
} else {
if ($taxa_histories{$taxon}->{$mutated_site}) { # this taxon HAS the mutated site
my $mutation_history = $taxa_histories{$taxon}->{$mutated_site};
#print "mutation_history=$mutation_history\n";
my @mutation_history_events = split(/,/, $mutation_history);
my $extant_nt = substr($mutation_history, -1);
#print "extant_nt=$extant_nt\n";
# Store nucleotide
$site_to_alleles{$mutated_site}->{$extant_nt}++;
foreach my $event (@mutation_history_events) { # these are ordered, but won't matter with new approach
if ($event =~ /(\d+)\-\w\>\w/) {
#91404-A>G
#868627-G>A
my $generation = $1;
$site_to_alleles{$mutated_site}->{history}->{$generation}->{$event}++;
}
}
} else { # this taxon does NOT have the mutated site, add the ancestral (seed)
$site_to_alleles{$mutated_site}->{$AA}++;
}
}
}
}
# DETERMINE CONSENSUS SEQUENCE TO PRINT
my @nts = qw/A C G T/;
my $consensus_seq = $seed_seq;
foreach my $mutated_site (sort {$a <=> $b} keys %site_to_alleles) {
my $REF = '';
my $REF_count = 0;
# Remember, if it's a tie, the first alphabetically gets it.
foreach my $nt (@nts) {
if ($site_to_alleles{$mutated_site}->{$nt} > $REF_count) {
$REF = $nt;
$REF_count = $site_to_alleles{$mutated_site}->{$nt};
}
}
# Impute into consensus sequence
substr($consensus_seq, $mutated_site - 1, 1, $REF);
}
unless($suppress_consensus_seq) { print "\nCONS_SEQUENCE: $consensus_seq\n" }
######################################################################################
# INITIATE VCF FILE
my $header_VCF = '';
open(OUT_TREVOLVER_VCF, ">>$vcf_output");
$header_VCF .= "##fileformat=VCFv4.1\n" .
"##FILTER=<ID=PASS,Description=\"All filters passed\">\n" .
"##fileDate=$today\n" .
"##reference=https://github.com/chasewnelson/trevolver\n" .
"##source=<TREVOLVER,Description=\"trevolver.pl @commands\">\n" .
"##tree=$tree\;\n" .
"##seed_sequence_file=$seed_sequence\n";
if ($input_seq ne '') {
unless($suppress_input_seq) {
$header_VCF .= "##inpt_sequence=$input_seq\n";
}
}
unless($suppress_seed_seq) {
$header_VCF .= "##seed_sequence=$seed_seq\n";
}
unless($suppress_consensus_seq) {
$header_VCF .= "##cons_sequence=$consensus_seq\n";
}
if ($outgroups) {
unless($suppress_MRCA_seq) {
$header_VCF .= "##MRCA_sequence=$MRCA_seq\n";
}
$header_VCF .= "##MRCA_generation=$MRCA_generation\n" .
"##MRCA_node_id=$MRCA_node_id\n" .
"##MRCA_subtree=$MRCA_subtree\n";
}
$header_VCF .= "##rate_matrix=$rate_matrix\n" .
"##branch_unit=$branch_unit\n" .
"##random_seed=$random_seed\n";
if ($tracked_motif) {
$header_VCF .= "##tracked_motif=$tracked_motif\n";
}
if ($burn_in) {
$header_VCF .= "##burn_in_length=$burn_in\n";
$header_VCF .= "##burn_in_mutations=$num_burn_in_mutations\n";
}
$header_VCF .= "##total_mutations=$num_mutations\n" .
"##tree_length=$total_branch_length\n" .
"##experiment_length=$root_to_tip_length\n" .
"##simulation_time=" . (time - $time1) . "\n" .
"##contig=<ID=$file_prefix,assembly=1,length=$seed_seq_length>\n" .
"##FORMAT=<ID=GT,Number=1,Type=String,Description=\"Genotype\">\n" .
"##INFO=<ID=AC,Number=A,Type=Integer,Description=\"Total number of alternate alleles in called genotypes\">\n" .
"##INFO=<ID=AF,Number=A,Type=Float,Description=\"Estimated allele frequency in the range (0,1)\">\n" .
"##INFO=<ID=NS,Number=1,Type=Integer,Description=\"Number of samples with data, equivalent to number of extant sequences\">\n" .
"##INFO=<ID=AN,Number=1,Type=Integer,Description=\"Total number of alleles in called genotypes, equivalent to number of extant sequences\">\n" .
"##INFO=<ID=DP,Number=1,Type=Integer,Description=\"Total read depth; here, equivalent to number of extant sequences\">\n" .
"##INFO=<ID=AA,Number=1,Type=String,Description=\"Ancestral Allele. AA: Ancestral allele, REF:Reference Allele, ALT:Alternate Allele\">\n" .
"##INFO=<ID=MRCA,Number=1,Type=String,Description=\"Most Recent Common Ancestor Allele of the ingroup\">\n" .
"##INFO=<ID=VT,Number=.,Type=String,Description=\"indicates what type of variant the line represents\">\n" .
"##INFO=<ID=MUTATIONS,Number=.,Type=String,Description=\"unique mutations that occurred at this site\">\n" .
"##INFO=<ID=MUTATIONS_OG,Number=.,Type=String,Description=\"unique mutations that occurred at this site in the outgroup(s)\">\n" .
"##INFO=<ID=GENERATIONS,Number=.,Type=String,Description=\"the generations at which unique mutations occurred at this site\">\n" .
"##INFO=<ID=GENERATIONS_OG,Number=.,Type=String,Description=\"the generations at which unique mutations occurred at this site in the outgroup(s)\">\n" .
"##INFO=<ID=TAXA,Number=.,Type=String,Description=\"the number of extant taxa (leaves) sharing the unique mutations that occurred at this site\">\n" .
"##INFO=<ID=TAXA_OG,Number=.,Type=String,Description=\"the number of extant taxa (leaves) sharing the unique mutations that occurred at this site among the outgroup(s)\">\n" .
"##INFO=<ID=MULTIHIT,Number=0,Type=Flag,Description=\"indicates whether a site has experienced multiple hits, i.e., more than one mutation\">\n" .
"##INFO=<ID=MULTIH_OG,Number=0,Type=Flag,Description=\"indicates whether a site has experienced multiple hits in the outgroup(s)\">\n" .
"##INFO=<ID=MULTIALLELIC,Number=0,Type=Flag,Description=\"indicates whether a site is multi-allelic\">\n" .
"##INFO=<ID=MULTIA_OG,Number=0,Type=Flag,Description=\"indicates whether a site is multi-allelic among the outgroup(s)\">\n" .
"##INFO=<ID=BACK_MUTATION,Number=0,Type=Flag,Description=\"indicates whether a site has experienced back mutation, i.e., return to a previous state via MULTIHIT\">\n" .
"##INFO=<ID=BACK_M_OG,Number=0,Type=Flag,Description=\"indicates whether a site has experienced back mutation in the outgroup(s)\">\n" .
"##INFO=<ID=RECURRENT_MUTATION,Number=0,Type=Flag,Description=\"indicates whether a site has experienced recurrent mutation, i.e., the same change occurring multiple times independently\">\n" .
"##INFO=<ID=RECURRENT_M_OG,Number=0,Type=Flag,Description=\"indicates whether a site has experienced recurrent mutation within the outgroup(s)\">\n" .
"##INFO=<ID=INVARIANT_ANCESTRAL,Number=0,Type=Flag,Description=\"indicates a site has no polymorphism in the ingroup, and that the fixed state matches the ancestral allele\">\n" .
"##INFO=<ID=INVARIANT_DERIVED,Number=0,Type=Flag,Description=\"indicates a site has no polymorphism in the ingroup, and that the fixed state matches a derived allele that resulted from mutation\">\n" .
"##INFO=<ID=NO_ANCESTRAL,Number=0,Type=Flag,Description=\"indicates that no ancestral (seed) alleles remain in the extant individuals of the ingroup\">\n" .
"##INFO=<ID=ALLELES_OG,Number=.,Type=String,Description=\"list of all alleles present in the outgroup(s)\">\n" .
"##INFO=<ID=ALLELE_COUNTS_OG,Number=.,Type=String,Description=\"list of all allele counts for alleles present in the outgroup(s), in the same order as ALLELES_OG\">\n" .
"##INFO=<ID=REF_OG,Number=.,Type=String,Description=\"the consensus (major) allele of outgroup(s), which may or may not match the AA\">\n" .
"##INFO=<ID=REF_OG_COUNT,Number=.,Type=Integer,Description=\"count of outgroup allele matching the outgroup consensus\">\n" .
"##INFO=<ID=REF_OG_AF,Number=.,Type=Float,Description=\"frequency of outgroup allele matching the outgroup consensus\">\n" .
"##INFO=<ID=OG_FIXED,Number=0,Type=Flag,Description=\"indicates that a site is fixed for one allele in the outgroup(s)\">\n" .
"##INFO=<ID=OG_DIVERGED,Number=0,Type=Flag,Description=\"indicates that one or more outgroup alleles differs from one or more ingroup alleles\">\n" .
"##INFO=<ID=OG_SHARE,Number=0,Type=Flag,Description=\"indicates one or more outgroup alleles matches one or more ingroup alleles\">\n" .
"#CHROM\tPOS\tID\tREF\tALT\tQUAL\tFILTER\tINFO\n";
print OUT_TREVOLVER_VCF "$header_VCF";
foreach my $taxon (sort {$a <=> $b} keys %taxa_histories) {
# OUTGROUP(S), if any
if ($excluded_taxa_names{$taxon}) { # exclude outgroups
$num_outgroups++; # COMEBACK -- we don't appear to be using these anymore. Consider pitching.
# INGROUP (all if no outgroups)
} else {
$num_taxa++; # COMEBACK -- will this capture ALL taxa in ALL situations? What if no history? I think yes.
}
} # end all taxa
my $out_line = '';
#my %multi_hit;
foreach my $mutated_site (sort {$a <=> $b} keys %site_to_alleles) {
#print "mutated_site=$mutated_site\n";
# AA
my $AA = substr($seed_seq, $mutated_site - 1, 1);
# MRCA ALLELE
my $MRCA_ALLELE = substr($MRCA_seq, $mutated_site - 1, 1);
#print "AA=$AA\n";
# Define REF as the major (consensus) allele
my $REF = '';
my $REF_count = 0;
my $arbitrary_REF = 0;
foreach my $nt (@nts) {
if ($site_to_alleles{$mutated_site}->{$nt} > $REF_count) {
$REF = $nt;
$REF_count = $site_to_alleles{$mutated_site}->{$nt};
$arbitrary_REF = 0;
} elsif ($site_to_alleles{$mutated_site}->{$nt} == $REF_count) {
$arbitrary_REF = 1;
}
}
#print "REF=$REF\n";
my $ALT = '';
my $AC = '';
my $AN_NS_DP = 0;
my $num_alleles = 0;
my @all_nts_present;
foreach my $nt (@nts) {
#print "nt=$nt\n";
if ($site_to_alleles{$mutated_site}->{$nt} > 0) { # here, possible that back mutation eliminates variation
#print "nt=$nt\n";
push(@all_nts_present, $nt);
$AN_NS_DP += $site_to_alleles{$mutated_site}->{$nt};
$num_alleles++;
if ($nt ne $REF) {
$ALT .= "$nt\,";
$AC .= $site_to_alleles{$mutated_site}->{$nt} . ',';
}
}
}
# This will only happen if the sample is 100% REF; print it
if ($ALT eq '' && $AC eq '') {
$ALT = "$REF\,";
$AC = "$AN_NS_DP\,";
}
chop($ALT);
chop($AC);
#print "ALT=$ALT\nAC=$AC\n";
# AFs
my $AF = '';
foreach my $nt (@nts) {
if ($nt ne $REF && $site_to_alleles{$mutated_site}->{$nt} > 0) {
my $this_AF = $site_to_alleles{$mutated_site}->{$nt} / $AN_NS_DP;
$AF .= "$this_AF\,";
}
}
# This will only happen if the sample is 100% REF; print it
if ($AF eq '') {
$AF = "1\,";
}
chop($AF);
$out_line .= "$fasta_header\t$mutated_site\t.\t$REF\t$ALT\t100\tPASS\t";
$out_line .= "AC=$AC\;AF=$AF\;AN=$AN_NS_DP\;NS=$AN_NS_DP\;DP=$AN_NS_DP\;AA=$AA\;";
if ($outgroups) { $out_line .= "MRCA=$MRCA_ALLELE\;" }
$out_line .= "VT=SNP\;";
##################################################################################
# INGROUP (SNP) INFORMATION
my $mutations = '';
my $generations = '';
my $taxa = '';
my $hits = 0;
my %prev_change;
my %prev_state_1;
my %prev_state_2;
my $back_mutation = 0;
my $recurrent_mutation = 0;
foreach my $generation (sort {$a <=> $b} keys %{$site_to_alleles{$mutated_site}->{history}}) {
#$site_to_alleles{$mutated_site}->{history}->{$generation}->{$event}++;
$hits++;
# SHOULD ONLY BE ONE EVENT PER GENERATION
foreach my $event (%{$site_to_alleles{$mutated_site}->{history}->{$generation}}) {
my $event_num = $site_to_alleles{$mutated_site}->{history}->{$generation}->{$event};
if($event =~ /(\d+)\-([\>\w+]+)/) {
my $this_mutation = $2;
$mutations .= "$2\,";
$generations .= "$1\,";
$taxa .= $event_num . ',';
my @two_states = split(/>/, $this_mutation);
my $state1 = $two_states[0];
my $state2 = $two_states[1];
# Could be recurrent/parallel
if ($prev_change{$this_mutation}) {
$recurrent_mutation++;
}
$prev_change{$this_mutation}++;
# Could be back mutation
if ($prev_state_1{$state2}) {
$back_mutation++;
}
$prev_state_1{$state1}++;
$prev_state_2{$state2}++;
}
}
}
chop($mutations);
chop($generations);
chop($taxa);
if ($mutations ne '' || $generations ne '' || $taxa ne '') {
$out_line .= "MUTATIONS=$mutations\;GENERATIONS=$generations\;TAXA=$taxa\;";
}
##################################################################################
# OUTGROUP (SUB) INFORMATION
my $mutations_out = '';
my $generations_out = '';
my $taxa_out = '';
my $hits_out = 0;
my %prev_change_out;
my %prev_state_1_out;
my %prev_state_2_out;
my $back_mutation_out = 0;
my $recurrent_mutation_out = 0;
if ($outgroups) {
foreach my $generation (sort {$a <=> $b} keys %{$site_to_outgroups{$mutated_site}->{history}}) {
$hits_out++;
# SHOULD ONLY BE ONE EVENT PER GENERATION
foreach my $event (%{$site_to_outgroups{$mutated_site}->{history}->{$generation}}) {
my $event_num = $site_to_outgroups{$mutated_site}->{history}->{$generation}->{$event};
if($event =~ /(\d+)\-([\>\w+]+)/) {
my $this_mutation = $2;
$mutations_out .= "$2\,";
$generations_out .= "$1\,";
$taxa_out .= $event_num . ',';
my @two_states = split(/>/, $this_mutation);
my $state1 = $two_states[0];
my $state2 = $two_states[1];
# Could be recurrent/parallel
if ($prev_change_out{$this_mutation}) {
$recurrent_mutation_out++;
}
$prev_change_out{$this_mutation}++;
# Could be back mutation
if ($prev_state_1_out{$state2}) {
$back_mutation_out++;
}
$prev_state_1_out{$state1}++;
$prev_state_2_out{$state2}++;
}
}
}
chop($mutations_out);
chop($generations_out);
chop($taxa_out);
if ($mutations_out ne '' || $generations_out ne '' || $taxa_out ne '') {
$out_line .= "MUTATIONS_OG=$mutations_out\;GENERATIONS_OG=$generations_out\;TAXA_OG=$taxa_out\;";
}
}
##################################################################################
# INGROUP (SNP) FLAGS
if ($arbitrary_REF == 1) {
$out_line .= "ARBITRARY_REF\;";
}
if ($hits > 1) {
$out_line .= "MULTIHIT\;";
}
if ($num_alleles > 2) {
$out_line .= "MULTIALLELIC\;";
}
if ($back_mutation > 0) {
$out_line .= "BACK_MUTATION\;";
}
if ($recurrent_mutation > 0) {
$out_line .= "RECURRENT_MUTATION\;";
}
if ($AF eq '1') {
if ($REF eq $AA) {
$out_line .= "INVARIANT_ANCESTRAL\;";
} else {
$out_line .= "INVARIANT_DERIVED\;";
}
}
if ($REF ne $AA) {
my $match_AA = 0;
foreach (@all_nts_present) {
if ($_ eq $AA) {
$match_AA = 1;
}
}
# Unless we have a match to the ancestral allele SOMEWHERE
unless ($match_AA == 1) {
$out_line .= "NO_ANCESTRAL\;";
}
}
##################################################################################
# OUTGROUP (SUB) FLAGS
if ($outgroups) {
# Define REF as the major (consensus) allele
my $REF_OG = '';
my $REF_OG_count = 0;
foreach my $nt (@nts) {
if ($site_to_outgroups{$mutated_site}->{$nt} > $REF_OG_count) {
$REF_OG = $nt;
$REF_OG_count = $site_to_outgroups{$mutated_site}->{$nt};
}
}
my $num_alleles_out = 0;
my $num_seqs_out = 0;
my @all_nts_present_out;
my $outgroup_alleles = '';
my $outgroup_counts = '';
foreach my $nt (@nts) {
if ($site_to_outgroups{$mutated_site}->{$nt} > 0) { # here, possible that back mutation eliminates variation
push(@all_nts_present_out, $nt);
$num_alleles_out++;