Appropriate algorithm for cell barcode and UMI error correction

[kbergin]

Current cell barcode correction methods lose some reads due to them having more than one error. We could implement another method that would allow us to quickly find cell barcode and UMI barcode errors that are greater than hamming distance one.

Suggestions:

• Ambrose has proposed a graph based method. This ticket represents the implementation of an adjacency structure (DFS directed graph) to be able to save these reads.
• We can work with Mark Fleharty to improve the currently used function of SortAndCorrectUmiMarkDuplicate function, in Picard tools, to effectively run on paired transcriptomic reads.
  • Mark Fleharty also suggested looking into the following tool (written in Scala) which can handle paired-transcriptomic reads, specifically the command GroupReadsByUmiC there in should the problem of the slow step. https://github.com/fulcrumgenomics/fgbio Tools for working with genomic and high throughput sequencing data. Website http://fulcrumgenomics.github.io/fgbio/

• CGATOxford/UMI-tools could be another choice, which is written in Python has UMI correction and duplication methods. Ian Sudbery from Sheffield Institute for Nucleic Acids, University of Sheffield, seems to be enthusiastic to point or help us explore this tool.

• Ambrose suggested looking into the barcode correction algorithm is described in the supplement of the paper Massively Parallel Single-Cell RNA-Seq for Marker-Free Decomposition of Tissues into Cell Types

AC

• [ ] Algorithm for cell and barcode correction that saves more reads by being able to correct more barcodes accurately.
• [ ] Completes processing most datasets within reasonable amount of time

[kbergin]

• We are going to confirm with Mark that this tool is scientifically functioning in the way we expect
• We would like to ask him if there is a way to re-sort the data to make this step go faster
• In the future, after benchmarking, we will do some comparison testing to improve this step

[kbergin]

@barkasn @kishorikonwar Tim suggests that this paper may have already benchmarked umi-tools vs alevin and may mean that we don't need to do benchmarking to choose a tool we could just use results from papers that have shown benchmarking. https://www.biorxiv.org/content/early/2018/06/01/335000

Perhaps there are other papers that have benchmarked this algorithm

[kbergin]

We have decided to implement umi-tools as a first pass and are communicating with the developers of Alevin for their help using their tool in the future. When they are ready we will put that into Optimus.