Robust Reconstruction of CRISPR and Tumor Lineage Using Depth Metrics

Lineage reconstruction using CRISPR edited barcodes are becoming wide-spread and methods robust against noise are in need. Neighbor-Joining (NJ) algorithm is a robust distance based algorithm extensively used in phylogeny field. NJ is also used for CRISPR-encoded-lineage (CEL) reconstruction with proper re-rooting since NJ is un-rooted algorithm. However, we found NJ works without re-rooting for reconstructing CEL when the lineage contains multiple trees but not for a single tree. Examining why this is the case leads to the idea of depth metrics. The notion of depth metrics also naturally explains why Russell-Rao metric, previously found best metric for CEL reconstruction, works well. Furthermore, based on the probabilistic model of CEL, we constructed a new metric that performs better than Russell-Rao metric. We also propose inferring ancestral code during reconstruction instead of using a linkage method. These, together with Nearest-Neighbor-Interchange resulted in a new robust method for reconstructing CEL or tumor-cell-lineages which share same assumptions as CEL.