Grow Lineages along Minimum Spanning Tree for B Cell Recptor Seqeuence Data

This page provides some examples of using source code version of GLaMST.

Prepare environment
Simulate data
Run GLaMST and visualize the results
Write Reconstructed Tree to File
Generate lineage tree from real data

Prepare environment

Set working directory to the upzipped folder. If your matlab does not have C/C++ compiler setup, need to first install MinGW, instructions at following link (Home->Add-Ons->search MinGW->install) https://www.mathworks.com/help/matlab/matlab_external/install-mingw-support-package.html

restoredefaultpath;
addpath lib
addpath src
mex src/editDist_only.cpp
mex src/backtrace.cpp

Building with 'Microsoft Visual C++ 2013 Professional'.
MEX completed successfully.
Building with 'Microsoft Visual C++ 2013 Professional'.
MEX completed successfully.

Simulate data

Simulate a dataset that

operation_probability = [0.99 0.005 0.005];% mutation, insertion, deletion chance
sequence_length = 300; % Length of the seqeunces
num_tree_nodes = 200; % Total number of the real tree
sample_size = 100; % Number of observed nodes
rng(42); %% Fix the random seed;
[observed_sequences, true_sequences, adj, is_selected] = simulate_data_v2(...
    sequence_length,num_tree_nodes,sample_size,operation_probability);
draw_hierarchy_tree(adj, is_selected');

Simulation:
    simulate a tree with 200 nodes, and 101 observed sequences (include root) ....   200
    obtained tree size: 144 nodes, 101 observed sequences.

Run GLaMST and visualize the results

This section is a example of using GLaMST. You need to pass a variable "observed_sequences" that contain a cell array of known sequences to function "reconstruct_tree_minimun_tree_size". Make sure the first sequence of "observed_sequences" should be root(G.L.). "reconstructed_nodes" is a cell array of sequences of the reconstructed tree. "reconstructed_is_selected" is the index of tree nodes that known before the reconstruction. "reconstructed_directed_adj" is the adjecent matrix that represent the hierarchical structure of the tree.

[reconstructed_nodes,mst_adj,reconstructed_is_selected, reconstructed_directed_adj] = ...
    reconstruct_tree_minimun_tree_size(observed_sequences);
draw_hierarchy_tree(reconstructed_directed_adj, reconstructed_is_selected);

Reconstruction:
    Initialization compute pairwise edit distance:   100 /   101Elapsed time is 2.120520 seconds.
    Iteratived build the tree:     1 /   100    Iteratived build the tree:     2 /   100Elapsed time is 0.124165 seconds.
    Iteratived build the tree:     3 /    99Elapsed time is 0.071267 seconds.
    Iteratived build the tree:     4 /    98Elapsed time is 0.069855 seconds.
    Iteratived build the tree:     5 /    98Elapsed time is 0.099349 seconds.
    Iteratived build the tree:     6 /    97Elapsed time is 0.060887 seconds.
    Iteratived build the tree:     7 /    96Elapsed time is 0.071146 seconds.
    Iteratived build the tree:     8 /    96Elapsed time is 0.109477 seconds.
    Iteratived build the tree:     9 /    96Elapsed time is 0.103427 seconds.
    Iteratived build the tree:    10 /    95Elapsed time is 0.061491 seconds.
    Iteratived build the tree:    11 /    95Elapsed time is 0.111595 seconds.
    Iteratived build the tree:    12 /    95Elapsed time is 0.114174 seconds.
    Iteratived build the tree:    13 /    94Elapsed time is 0.064371 seconds.
    Iteratived build the tree:    14 /    94Elapsed time is 0.113067 seconds.
    Iteratived build the tree:    15 /    93Elapsed time is 0.059393 seconds.
    Iteratived build the tree:    16 /    92Elapsed time is 0.059642 seconds.
    Iteratived build the tree:    17 /    91Elapsed time is 0.062090 seconds.
    Iteratived build the tree:    18 /    91Elapsed time is 0.099319 seconds.
    Iteratived build the tree:    19 /    90Elapsed time is 0.100453 seconds.
    Iteratived build the tree:    20 /    90Elapsed time is 0.120444 seconds.
    Iteratived build the tree:    21 /    89Elapsed time is 0.058099 seconds.
    Iteratived build the tree:    22 /    88Elapsed time is 0.063789 seconds.
    Iteratived build the tree:    23 /    87Elapsed time is 0.064429 seconds.
    Iteratived build the tree:    24 /    87Elapsed time is 0.099779 seconds.
    Iteratived build the tree:    25 /    86Elapsed time is 0.059487 seconds.
    Iteratived build the tree:    26 /    86Elapsed time is 0.100215 seconds.
    Iteratived build the tree:    27 /    85Elapsed time is 0.056506 seconds.
    Iteratived build the tree:    28 /    84Elapsed time is 0.054996 seconds.
    Iteratived build the tree:    29 /    83Elapsed time is 0.054777 seconds.
    Iteratived build the tree:    30 /    83Elapsed time is 0.096124 seconds.
    Iteratived build the tree:    31 /    83Elapsed time is 0.101616 seconds.
    Iteratived build the tree:    32 /    82Elapsed time is 0.069621 seconds.
    Iteratived build the tree:    33 /    82Elapsed time is 0.103427 seconds.
    Iteratived build the tree:    34 /    82Elapsed time is 0.097281 seconds.
    Iteratived build the tree:    35 /    81Elapsed time is 0.054755 seconds.
    Iteratived build the tree:    36 /    81Elapsed time is 0.106548 seconds.
    Iteratived build the tree:    37 /    81Elapsed time is 0.128251 seconds.
    Iteratived build the tree:    38 /    80Elapsed time is 0.064422 seconds.
    Iteratived build the tree:    39 /    79Elapsed time is 0.056616 seconds.
    Iteratived build the tree:    40 /    79Elapsed time is 0.101563 seconds.
    Iteratived build the tree:    41 /    78Elapsed time is 0.056860 seconds.
    Iteratived build the tree:    42 /    77Elapsed time is 0.060619 seconds.
    Iteratived build the tree:    43 /    77Elapsed time is 0.115746 seconds.
    Iteratived build the tree:    44 /    76Elapsed time is 0.068366 seconds.
    Iteratived build the tree:    45 /    75Elapsed time is 0.068663 seconds.
    Iteratived build the tree:    46 /    75Elapsed time is 0.117909 seconds.
    Iteratived build the tree:    47 /    74Elapsed time is 0.067540 seconds.
    Iteratived build the tree:    48 /    74Elapsed time is 0.118054 seconds.
    Iteratived build the tree:    49 /    73Elapsed time is 0.080665 seconds.
    Iteratived build the tree:    50 /    73Elapsed time is 0.119379 seconds.
    Iteratived build the tree:    51 /    72Elapsed time is 0.060695 seconds.
    Iteratived build the tree:    52 /    71Elapsed time is 0.067304 seconds.
    Iteratived build the tree:    53 /    70Elapsed time is 0.070905 seconds.
    Iteratived build the tree:    54 /    69Elapsed time is 0.059287 seconds.
    Iteratived build the tree:    55 /    68Elapsed time is 0.056229 seconds.
    Iteratived build the tree:    56 /    68Elapsed time is 0.129641 seconds.
    Iteratived build the tree:    57 /    67Elapsed time is 0.055729 seconds.
    Iteratived build the tree:    58 /    67Elapsed time is 0.123387 seconds.
    Iteratived build the tree:    59 /    66Elapsed time is 0.069422 seconds.
    Iteratived build the tree:    60 /    65Elapsed time is 0.071501 seconds.
    Iteratived build the tree:    61 /    64Elapsed time is 0.057541 seconds.
    Iteratived build the tree:    62 /    63Elapsed time is 0.056594 seconds.
    Iteratived build the tree:    63 /    62Elapsed time is 0.055693 seconds.
    Iteratived build the tree:    64 /    61Elapsed time is 0.062871 seconds.
    Iteratived build the tree:    65 /    60Elapsed time is 0.060691 seconds.
    Iteratived build the tree:    66 /    59Elapsed time is 0.061530 seconds.
    Iteratived build the tree:    67 /    58Elapsed time is 0.057703 seconds.
    Iteratived build the tree:    68 /    57Elapsed time is 0.065252 seconds.
    Iteratived build the tree:    69 /    56Elapsed time is 0.062061 seconds.
    Iteratived build the tree:    70 /    56Elapsed time is 0.096273 seconds.
    Iteratived build the tree:    71 /    55Elapsed time is 0.052244 seconds.
    Iteratived build the tree:    72 /    54Elapsed time is 0.048066 seconds.
    Iteratived build the tree:    73 /    53Elapsed time is 0.063324 seconds.
    Iteratived build the tree:    74 /    52Elapsed time is 0.046920 seconds.
    Iteratived build the tree:    75 /    51Elapsed time is 0.044680 seconds.
    Iteratived build the tree:    76 /    50Elapsed time is 0.051277 seconds.
    Iteratived build the tree:    77 /    50Elapsed time is 0.095397 seconds.
    Iteratived build the tree:    78 /    49Elapsed time is 0.046078 seconds.
    Iteratived build the tree:    79 /    48Elapsed time is 0.047744 seconds.
    Iteratived build the tree:    80 /    47Elapsed time is 0.060355 seconds.
    Iteratived build the tree:    81 /    46Elapsed time is 0.041801 seconds.
    Iteratived build the tree:    82 /    45Elapsed time is 0.039797 seconds.
    Iteratived build the tree:    83 /    44Elapsed time is 0.042710 seconds.
    Iteratived build the tree:    84 /    44Elapsed time is 0.085207 seconds.
    Iteratived build the tree:    85 /    44Elapsed time is 0.086675 seconds.
    Iteratived build the tree:    86 /    43Elapsed time is 0.038661 seconds.
    Iteratived build the tree:    87 /    42Elapsed time is 0.037253 seconds.
    Iteratived build the tree:    88 /    42Elapsed time is 0.097452 seconds.
    Iteratived build the tree:    89 /    41Elapsed time is 0.041653 seconds.
    Iteratived build the tree:    90 /    41Elapsed time is 0.097539 seconds.
    Iteratived build the tree:    91 /    40Elapsed time is 0.046379 seconds.
    Iteratived build the tree:    92 /    40Elapsed time is 0.106827 seconds.
    Iteratived build the tree:    93 /    39Elapsed time is 0.042877 seconds.
    Iteratived build the tree:    94 /    39Elapsed time is 0.085487 seconds.
    Iteratived build the tree:    95 /    38Elapsed time is 0.034732 seconds.
    Iteratived build the tree:    96 /    38Elapsed time is 0.083450 seconds.
    Iteratived build the tree:    97 /    37Elapsed time is 0.037617 seconds.
    Iteratived build the tree:    98 /    36Elapsed time is 0.032874 seconds.
    Iteratived build the tree:    99 /    35Elapsed time is 0.033980 seconds.
    Iteratived build the tree:   100 /    34Elapsed time is 0.031642 seconds.
    Iteratived build the tree:   101 /    34Elapsed time is 0.078889 seconds.
    Iteratived build the tree:   102 /    33Elapsed time is 0.030038 seconds.
    Iteratived build the tree:   103 /    32Elapsed time is 0.028862 seconds.
    Iteratived build the tree:   104 /    31Elapsed time is 0.028024 seconds.
    Iteratived build the tree:   105 /    30Elapsed time is 0.027379 seconds.
    Iteratived build the tree:   106 /    30Elapsed time is 0.075950 seconds.
    Iteratived build the tree:   107 /    29Elapsed time is 0.027410 seconds.
    Iteratived build the tree:   108 /    28Elapsed time is 0.026308 seconds.
    Iteratived build the tree:   109 /    28Elapsed time is 0.076572 seconds.
    Iteratived build the tree:   110 /    27Elapsed time is 0.025357 seconds.
    Iteratived build the tree:   111 /    26Elapsed time is 0.024686 seconds.
    Iteratived build the tree:   112 /    26Elapsed time is 0.075524 seconds.
    Iteratived build the tree:   113 /    25Elapsed time is 0.023901 seconds.
    Iteratived build the tree:   114 /    24Elapsed time is 0.023800 seconds.
    Iteratived build the tree:   115 /    23Elapsed time is 0.022777 seconds.
    Iteratived build the tree:   116 /    22Elapsed time is 0.021790 seconds.
    Iteratived build the tree:   117 /    21Elapsed time is 0.021194 seconds.
    Iteratived build the tree:   118 /    21Elapsed time is 0.077023 seconds.
    Iteratived build the tree:   119 /    20Elapsed time is 0.020023 seconds.
    Iteratived build the tree:   120 /    19Elapsed time is 0.019134 seconds.
    Iteratived build the tree:   121 /    18Elapsed time is 0.018273 seconds.
    Iteratived build the tree:   122 /    17Elapsed time is 0.017469 seconds.
    Iteratived build the tree:   123 /    16Elapsed time is 0.016294 seconds.
    Iteratived build the tree:   124 /    15Elapsed time is 0.015403 seconds.
    Iteratived build the tree:   125 /    14Elapsed time is 0.014402 seconds.
    Iteratived build the tree:   126 /    13Elapsed time is 0.015432 seconds.
    Iteratived build the tree:   127 /    12Elapsed time is 0.012567 seconds.
    Iteratived build the tree:   128 /    11Elapsed time is 0.012041 seconds.
    Iteratived build the tree:   129 /    10Elapsed time is 0.011227 seconds.
    Iteratived build the tree:   130 /    10Elapsed time is 0.061735 seconds.
    Iteratived build the tree:   131 /     9Elapsed time is 0.011292 seconds.
    Iteratived build the tree:   132 /     8Elapsed time is 0.010715 seconds.
    Iteratived build the tree:   133 /     7Elapsed time is 0.009226 seconds.
    Iteratived build the tree:   134 /     6Elapsed time is 0.008496 seconds.
    Iteratived build the tree:   135 /     5Elapsed time is 0.008101 seconds.
    Iteratived build the tree:   136 /     5Elapsed time is 0.064753 seconds.
    Iteratived build the tree:   137 /     4Elapsed time is 0.007499 seconds.
    Iteratived build the tree:   138 /     4Elapsed time is 0.057080 seconds.
    Iteratived build the tree:   139 /     3Elapsed time is 0.009390 seconds.
    Iteratived build the tree:   140 /     3Elapsed time is 0.069162 seconds.
    Iteratived build the tree:   141 /     2Elapsed time is 0.007184 seconds.
    Iteratived build the tree:   142 /     1Elapsed time is 0.009011 seconds.
    Iteratived build the tree:   143 /     0Elapsed time is 0.005143 seconds.
    Trim the tree for un-necessary nodes ... 
    Rewire the tree to further reduce size ... 143

Write Reconstructed Tree to File

Use the command below to write the reconstructed tree to file. This command will generate two files. In simulated.out.tree file, each row coresponds to one single node. First item each row is node name and the following items are its children. In simulated.out.fa file, all the observed sequences and inserted seqeunces are presented.

Write_tree_toFile(reconstructed_nodes, reconstructed_directed_adj, reconstructed_is_selected, 'simulated');

Generate lineage tree from real data

Given this data is not yet publicly avaliable, we have simulated a dataset that has exactly the same topology as used in our paper ( with sequences order shuffled and nucleobase exchenged). This simulated data is avaliable here https://github.com/xysheep/GLaMST/blob/master/demodata.

fsa = fastaread('demodata/real.fasta');
observed_sequences = {fsa.Sequence}';

[reconstructed_nodes,mst_adj,reconstructed_is_selected, reconstructed_directed_adj] = ...
    reconstruct_tree_minimun_tree_size(observed_sequences);
draw_hierarchy_tree(reconstructed_directed_adj, reconstructed_is_selected);