Difference between revisions of "Team:Edinburgh UG/Error Correction"

A checksum is a commonly used technique in network engineering that we’ve adapted for use in DNA storage. In this format the checksum allows the detection of errors in a BabbleBlock (DNA sentence). The checksum holds the sum of the word coding regions of BabbleBricks (DNA words) in a BabbleBlock in a 4 BabbleBrick region that can be found towards the end of a BabbleBlock.

When a BabbleBlock is being translated the checksum is looked at first to see if it matches the sums of the word coding regions in the DNA we get back from sequencing. If this is the case, no errors have appeared and the translation program can proceed as normal however if there is no match an error has occurred somewhere in the BabbleBlock and other error correcting mechanisms will have to be used to make sure the stored information can still be read back.

Currently a checksum utilizes only a small percentage of the values that can be stored. A BabbleBrick contains 5 base 4 digits meaning that 4^5B unique bits of information share one of 15B checksums where B is the amount of BabbleBricks in one BabbleBlock. This data has been plotted for BabbleBlocks containing 2 and 3 BabbleBricks in Fig.1 and Fig.2 respectively. Assuming that between the time of writing and reading any number of mutations can occur, the maximum probability of a mutation event resulting in the same checksum can be calculated by comparing the frequency of one checksum to the total frequency of unique bits of information.

Therefore, it can be predicted that for an average sentence containing 9 words the maximum probability of the same checksum occurring will be of the magnitude of 1%. The probability should decrease marginally when adding BabbleBricks due to the slightly increased range of checksums that become available. This value can be optimized by altering the method of the checksum to utilize a greater range of values and to spread out the frequency more evenly as to reduce the maximum probability of the same checksum occurring.

Currently one BabbleBlock has 4 BabbleBricks dedicated to storing the checksum, giving a maximum 10^4 possible values. The first step in determining a ‘CheckMethod’ is to ensure that all checksums for a suitable amount of BabbleBricks can be stored without going over 10^4. It is also important to not use operators that will result in negative numbers or decimals, therefore limiting the possible checksum values to integers up to but not including 10^4, this rules out operators such as subtract and divide. For this example, a suitable number of words in a sentence and therefore BabbleBricks in a BabbleBlock shall be 20. All simulations will be carried out on 3 BabbleBrick systems due to computing limitations.

Checksums are non-directional, for example a BabbleBrick of bases [2,2,2,2,2] would have the same checksum as [2,1,3,2,2]. To alter this a checkmethod will incorporate the position of the base in to the calculation. At each point the digit is multiplied by its position in the BabbleBlock, where the first BabbleBrick has digit positions 1 to 5 and the last BabbleBrick (20th}) has positions 96 to 100. A scaler alpha has been included to increase the range of results. To ensure multiplications don’t result in a null result the value of each base had a value of 1 added to it. The first checkmethod of one BabbleBlock can be defined as: