Synthetic Biology:Vectors/Barcode - Revision history

Etienne Robillard: /* Overview */

Etienne Robillard — Tue, 11 Dec 2012 14:45:05 GMT

Overview

←Older revision		Revision as of 14:45, 11 December 2012
Line 7:		Line 7:
	#'''Detection''': to enable detection of standard biological parts in arbitrary DNA samples. For instance, users wish to detect cases of misuse of parts.		#'''Detection''': to enable detection of standard biological parts in arbitrary DNA samples. For instance, users wish to detect cases of misuse of parts.
	#'''Identification''': to enable identification of biological parts, devices and systems. Such identification may also involve determining the original designer. For instance, users wish to quickly identify the vector in which their part resides in a typical sequencing reaction.		#'''Identification''': to enable identification of biological parts, devices and systems. Such identification may also involve determining the original designer. For instance, users wish to quickly identify the vector in which their part resides in a typical sequencing reaction.
-	#'''Authentication''': to enable verification the integrity of a DNA sequence. Such a barcode would allow users to check for naturally-occuring or human-induced mutations.	+	#'''Authentication''': to enable verification of the integrity of a DNA sequence. Such a barcode would allow users to check for naturally-occuring or human-induced mutations.

	There are a couple schemes for barcoding that have been implemented on a trial basis or proposed.		There are a couple schemes for barcoding that have been implemented on a trial basis or proposed.

Austin J. Che: /* Scheme to encode bit strings */

Austin J. Che — Fri, 21 Apr 2006 12:46:38 GMT

Scheme to encode bit strings

←Older revision		Revision as of 12:46, 21 April 2006
Line 50:		Line 50:
	Check out the world's first [[Illegal DNA sequence]].		Check out the world's first [[Illegal DNA sequence]].

-	The general encoding/decoding method: Each byte of 8 bits is split into 4x2 bits. Each pair of bits at each location is mapped to some nucleotide. For example 00 at position 0 could be mapped to A, 01 at position 1 to T, 00 at position 1 to T, etc. To be decodable, there must be a 1 to 1 mapping at each position from 2 bits to 4 nucleotides. But this leaves <math>24^4</math> different ways to do this type of encoding. ~~Currently, I pick~~ a ~~particular encoding that for some common things that Reshma would like~~ to encode ~~(plasmid names~~, ~~parts, etc. in ASCII) have~~ the following properties:	+	The general encoding/decoding method: Each byte of 8 bits is split into 4x2 bits. Each pair of bits at each location is mapped to some nucleotide. For example 00 at position 0 could be mapped to A, 01 at position 1 to T, 00 at position 1 to T, etc. To be decodable, there must be a 1 to 1 mapping at each position from 2 bits to 4 nucleotides. But this leaves <math>24^4</math> different ways to do this type of encoding. Given a string to encode, all possible encodings are looked at and the encoding with the best following properties are used:
	* %GC close to 50%		* %GC close to 50%
	* %GT as high as possible (biased nucleotide use).		* %GT as high as possible (biased nucleotide use).

-	Biasing the nucleotides makes it less likely for restriction sites or other secondary structures to appear. ~~In addition~~, ~~it allows for an easier choice of an escape sequence. The idea is to have~~ a ~~family of escape sequences, for example ACNNNAC, which~~ can be ~~inserted anywhere you want. This allows you to modify~~ the %GC content if desired, break up bad sequences, or whatever else by inserting arbitrary non-coding sequence. If the escape occurs in the real sequence, it gets escaped itself. Escapes have not been chosen or implemented yet.	+	Biasing the nucleotides makes it less likely for restriction sites or other secondary structures to appear. At the beginning of the encoded string, we attach the encoding table as a simple fixed 12nt (4x3 nt as the 4th nucleotide can be derived from the first 3).

-	~~Another idea I had was to try all possible encodings and pick~~ the ~~one that provided~~ the ~~best properties that one wants~~. At the beginning ~~(as~~ the ~~start~~ code)~~, we print~~ the encoding ~~(would take a fixed 12nt)~~.	+	The current escape sequence is simply 'AC'. As the encoded string is GT biased, the occurrence of AC turns out to be fairly low. If AC occurs in the encoded sequence, it gets escaped itself with another copy, e.g. AC->ACAC. All other escape sequences begin with AC followed by some sequence. For example, currently we have an escape sequence to represent the beginning and end of the code. There are also escape sequences that allows insertion of arbitrary sequence ('comments?') into the encoding. This allows you to modify the %GC content if desired, break up bad sequences, or whatever else by inserting arbitrary non-coding sequence.

	Randy suggested some form of compression. Not sure how much space we save or how much more complex it would make the algorithm.		Randy suggested some form of compression. Not sure how much space we save or how much more complex it would make the algorithm.
		+
		+	Adding the ability to correct base mutations in the DNA (on the computer not in vivo) is possible and a Reed-Solomon code is the most promising candidate code (not implemented yet). Being resistant to frameshifts appears to be more difficult.

	This algorithm provides the ability to encode anything such as Unicode, pictures, or anything else under the sun. Is the complexity and increase in size worth this capability?		This algorithm provides the ability to encode anything such as Unicode, pictures, or anything else under the sun. Is the complexity and increase in size worth this capability?

Reshma P. Shetty at 03:45, 19 April 2006

Reshma P. Shetty — Wed, 19 Apr 2006 03:45:45 GMT

←Older revision		Revision as of 03:45, 19 April 2006
Line 33:		Line 33:
	#'''Barcodes should be sequenceable.'''		#'''Barcodes should be sequenceable.'''
	#'''Barcodes should have some mechanism for detecting and/or correcting for errors due to mutation.''' Additional bases are needed for error detection and correction which can lengthen barcode length.		#'''Barcodes should have some mechanism for detecting and/or correcting for errors due to mutation.''' Additional bases are needed for error detection and correction which can lengthen barcode length.
-	#*~~'''[[User:Austin\|Austin]] 21:27, 18 April 2006 (EDT)''': ECC for normal mutations is~~ relatively ~~easy. Frameshifts however are difficult. I contacted Robert Gallager about this problem and this is what he responded~~ with ~~(I haven't had the time or energy to figure any more of this out):~~	+	#*Mutations are relatively straightforward to cope with using standard coding theory. However, frameshift mutations are far more tricky to deal with. See [[Talk:Synthetic Biology:Vectors/Barcode]] for details.
-	~~: You have picked a difficult problem for yourself. Almost all of~~ coding theory ~~is done using the assumption of perfect timing~~. ~~I worked on this problem back in 1961 and wrote a short technical note on it~~. ~~You can find a very poor copy of it on my website (http~~://web.mit.edu/gallager/www/). It is the 3rd entry under Internal memoranda in my publication list. You will have to find out something about convolutional codes and sequential decoding to make sense of it, so it might not be worth your effort. I don't think that having an alphabet size of 4 rather than 2 is a major difference. I haven't seen anything else in the literature dealing with this problem, although I haven't been looking. It is sensible to restrict yourself to single anomalies, but the decoder has no block structure and thus no way to define a single anomaly. That is why I looked at convolutional codes back in 61, since the block structure problem was avoided. Gallager, R. G., "Sequential Decoding for ~~Binary Channels with Noise and Synchronization Errors", Lincoln Group Report, 2502, Summer 1961~~.	+
-		+

	Austin's barcode scheme to encode bit strings below represents an attempt to address many of these issues.		Austin's barcode scheme to encode bit strings below represents an attempt to address many of these issues.

Austin J. Che at 01:27, 19 April 2006

Austin J. Che — Wed, 19 Apr 2006 01:27:08 GMT

←Older revision		Revision as of 01:27, 19 April 2006
Line 33:		Line 33:
	#'''Barcodes should be sequenceable.'''		#'''Barcodes should be sequenceable.'''
	#'''Barcodes should have some mechanism for detecting and/or correcting for errors due to mutation.''' Additional bases are needed for error detection and correction which can lengthen barcode length.		#'''Barcodes should have some mechanism for detecting and/or correcting for errors due to mutation.''' Additional bases are needed for error detection and correction which can lengthen barcode length.
		+	#*'''[[User:Austin\|Austin]] 21:27, 18 April 2006 (EDT)''': ECC for normal mutations is relatively easy. Frameshifts however are difficult. I contacted Robert Gallager about this problem and this is what he responded with (I haven't had the time or energy to figure any more of this out):
		+	: You have picked a difficult problem for yourself. Almost all of coding theory is done using the assumption of perfect timing. I worked on this problem back in 1961 and wrote a short technical note on it. You can find a very poor copy of it on my website (http://web.mit.edu/gallager/www/). It is the 3rd entry under Internal memoranda in my publication list. You will have to find out something about convolutional codes and sequential decoding to make sense of it, so it might not be worth your effort. I don't think that having an alphabet size of 4 rather than 2 is a major difference. I haven't seen anything else in the literature dealing with this problem, although I haven't been looking. It is sensible to restrict yourself to single anomalies, but the decoder has no block structure and thus no way to define a single anomaly. That is why I looked at convolutional codes back in 61, since the block structure problem was avoided. Gallager, R. G., "Sequential Decoding for Binary Channels with Noise and Synchronization Errors", Lincoln Group Report, 2502, Summer 1961.
		+

	Austin's barcode scheme to encode bit strings below represents an attempt to address many of these issues.		Austin's barcode scheme to encode bit strings below represents an attempt to address many of these issues.

Reshma P. Shetty: added overview, please revise as you see fit

Reshma P. Shetty — Wed, 19 Apr 2006 01:04:45 GMT

added overview, please revise as you see fit

←Older revision		Revision as of 01:04, 19 April 2006
Line 1:		Line 1:
-	==Barcode scheme to encode bit strings==	+	==Overview==
		+
		+	The MIT SBWG has been discussing the barcoding of engineered biological systems for a while. An initial attempt (described at [[Barcodes]]) was made to implement barcodes on many BioBrick coding regions. Here is a quick (and likely incomplete) overview on some of the issues surrounding barcodes.
		+
		+	As Drew has [[Talk:Synthetic Biology:Vectors/Barcode \| initially suggested]], there are three basic purposes for barcoding synthetic systems.
		+
		+	#'''Detection''': to enable detection of standard biological parts in arbitrary DNA samples. For instance, users wish to detect cases of misuse of parts.
		+	#'''Identification''': to enable identification of biological parts, devices and systems. Such identification may also involve determining the original designer. For instance, users wish to quickly identify the vector in which their part resides in a typical sequencing reaction.
		+	#'''Authentication''': to enable verification the integrity of a DNA sequence. Such a barcode would allow users to check for naturally-occuring or human-induced mutations.
		+
		+	There are a couple schemes for barcoding that have been implemented on a trial basis or proposed.
		+
		+	#The [[Barcodes \| original barcodes scheme]] enabled quick detection of BioBricks via PCR methods. It is not clear that detection-based barcodes are necessary given the ease with which sequencing can be done.
		+	#The barcode schemes described below are primarily for the purpose of identifying BioBricks. Since the scheme proposed by Austin is able to encode arbitrary bit strings, such a barcode would permit inline documentation of anything include
		+	#*BioBrick part number
		+	#*URL or doi number
		+	#*designer
		+	#*inline comments
		+	#There is no available proposal to accomplish the third goal of authentication.
		+
		+	A universal barcoding scheme is difficult to implement for several reasons.
		+
		+	#'''Barcodes should be biologically innocuous.''' Ideally, barcodes should not be DNA sequences that will encode a biological function including but not limited to the following.
		+	#*initiate transcription (be a promoter)
		+	#*contain coding sequences
		+	#*initiate translation
		+	#*have secondary structure
		+	#*have restriction enzyme cut sites
		+	#*have too many repetitive elements
		+	#*have too many strings of a single nucleotide or strings of purines/pyrimidines.
		+	#'''Barcodes should not be sequences that interfere with system function.''' There must be a mechanism to insert "escape sequences" to interrupt system-specific meaningful sequences.
		+	#'''Barcodes should not be too long.''' Long sequences can add to fabrication costs and may impact system function.
		+	#'''Barcodes should be sequenceable.'''
		+	#'''Barcodes should have some mechanism for detecting and/or correcting for errors due to mutation.''' Additional bases are needed for error detection and correction which can lengthen barcode length.
		+
		+	Austin's barcode scheme to encode bit strings below represents an attempt to address many of these issues.
		+
		+	==Scheme to encode bit strings==

	Enable encoding of arbitrary bit strings into DNA without introducing "biologically bad" sequences. (Tom and Austin).		Enable encoding of arbitrary bit strings into DNA without introducing "biologically bad" sequences. (Tom and Austin).
Line 24:		Line 61:
	This algorithm provides the ability to encode anything such as Unicode, pictures, or anything else under the sun. Is the complexity and increase in size worth this capability?		This algorithm provides the ability to encode anything such as Unicode, pictures, or anything else under the sun. Is the complexity and increase in size worth this capability?

-	==~~Barcode scheme~~ to encode text only==	+	==Scheme to encode text only==

	===Case-sensitive codon tables===		===Case-sensitive codon tables===

Reshma P. Shetty: /* Barcode scheme to encode bit strings */

Reshma P. Shetty — Sat, 15 Apr 2006 21:42:44 GMT

Barcode scheme to encode bit strings

←Older revision		Revision as of 21:42, 15 April 2006
Line 9:		Line 9:

	I've put up a test page for playing with encoding binary into DNA at http://synbio.mit.edu/tools/encoder.cgi		I've put up a test page for playing with encoding binary into DNA at http://synbio.mit.edu/tools/encoder.cgi
		+
		+	Check out the world's first [[Illegal DNA sequence]].

	The general encoding/decoding method: Each byte of 8 bits is split into 4x2 bits. Each pair of bits at each location is mapped to some nucleotide. For example 00 at position 0 could be mapped to A, 01 at position 1 to T, 00 at position 1 to T, etc. To be decodable, there must be a 1 to 1 mapping at each position from 2 bits to 4 nucleotides. But this leaves <math>24^4</math> different ways to do this type of encoding. Currently, I pick a particular encoding that for some common things that Reshma would like to encode (plasmid names, parts, etc. in ASCII) have the following properties:		The general encoding/decoding method: Each byte of 8 bits is split into 4x2 bits. Each pair of bits at each location is mapped to some nucleotide. For example 00 at position 0 could be mapped to A, 01 at position 1 to T, 00 at position 1 to T, etc. To be decodable, there must be a 1 to 1 mapping at each position from 2 bits to 4 nucleotides. But this leaves <math>24^4</math> different ways to do this type of encoding. Currently, I pick a particular encoding that for some common things that Reshma would like to encode (plasmid names, parts, etc. in ASCII) have the following properties:

Reshma P. Shetty at 16:45, 8 March 2006

Reshma P. Shetty — Wed, 08 Mar 2006 16:45:15 GMT

←Older revision		Revision as of 16:45, 8 March 2006
Line 385:		Line 385:
	*These codons may not be optimally spaced from one another? Tom doesn't think this matters.		*These codons may not be optimally spaced from one another? Tom doesn't think this matters.
	*Tom pointed out that the barcode should probably be as GC content neutral (i.e. try to avoid all AT or all GC codons).		*Tom pointed out that the barcode should probably be as GC content neutral (i.e. try to avoid all AT or all GC codons).
-
-	~~==Early discussions==~~
-	~~Is there a plan for the barcode?~~
-	*Should the barcode only be readable by sequencing or is it sufficient to just look for an amplified band in a PCR reaction.
-	**If PCR is sufficient we could build in a unique sequence just before the BB prefix and then design a reverse primer to that sequence to use along with VF.
-	*It seems like the most likely short-mid term problem is that a researcher would be uncertain as to which BioBrick vector they had, rather than the doomsday question of trying to work out if there is a BioBrick vector somewhere in the drink that turned Drew's hair [[Barcodes\|pink]].
-	**Given this assumption, could we choose restriction sites, each of which are found uniquely in one of our BioBrick vectors? A researcher could just prep, digest and run on a gel to tell which vector they had.--[[User:Bcanton\|BC]]
-	***It might be useful to be able to tell the plasmid (and resistance) by colony PCR rather than a prep. A PCR requires less starting material. -[[User:Jkm\|Jkm]]
-	*There is no current plan for the barcode. The intention was just to make the identity of the plasmid obvious from a sequencing reaction but this goal is compatible with making the plasmid identifiable via a colony PCR as well. Choosing a unique restriction site for each vector would be more difficult because that would involve placing additional requirements in the BioBricks standard. i.e. Parts cannot have any of the BioBrick enzymes nor this list of restriction enzymes that are identifiers for vectors. This doesn't seem practical to me. --[[Reshma Shetty \| RS]]
-	**I'm not in favor of inserting restriction sites but you can probably get away without using any new enzymes under certain assumptions. First let's assume one always inserts into a new plasmid (3-way ligation, either with or without 3 antibiotic selection). Then you can just insert various combinations of BioBrick enzymes into specific locations into the plasmids and look at the pattern of bands when you cut with them. The benefit of this is let's say you cut a part with ES, run on gel, and based on the band pattern from the plasmid, you know immediately which plasmid it's in, and if it's correct, you isolate the part band and can proceed with the assembly. You have the same problem as below if one of the plasmid pieces is the same length as the part, but now you may have more potential conflicting bands. 3-antibiotic assembly without purification shouldn't really be impacted by a couple more pieces of plasmid floating around. You can also take this idea by defining another single enzyme that will be used for this purpose and you can tell plasmids apart again by the differetn lengths generated after digest. So you definitely don't need one enzyme/plasmid.
-
-	~~One plan that I am currently considering is actually encoding the name of the plasmid in DNA.~~
-	~~For instance,~~
-
-	~~<font face="courier">~~
-	~~AAA = 0;~~
-	~~AAC = 1;~~
-	~~AAG = 2;~~
-	~~AAT = 3;~~
-	.
-	.
-	.
-	~~AGC = 9;~~
-	~~AGG = A;~~
-	~~AGT = B;~~
-	.
-	.
-	.
-	~~GAT = Z;~~
-	~~</font>~~
-
-	So that you could literally write out pSB5AC4-P1010.I50020 in DNA. Of course, we may want to make this slightly more intelligent to space out characters, include start and stop strings and avoid key codons like ATG, TAA and TGA. Any comments? --[[User:Rshetty\|RS]]

Reshma P. Shetty at 16:44, 8 March 2006

Reshma P. Shetty — Wed, 08 Mar 2006 16:44:37 GMT

←Older revision		Revision as of 16:44, 8 March 2006
Line 1:		Line 1:
-	==~~Alternative barcode~~==	+	==Barcode scheme to encode bit strings==

	Enable encoding of arbitrary bit strings into DNA without introducing "biologically bad" sequences. (Tom and Austin).		Enable encoding of arbitrary bit strings into DNA without introducing "biologically bad" sequences. (Tom and Austin).
Line 22:		Line 22:
	This algorithm provides the ability to encode anything such as Unicode, pictures, or anything else under the sun. Is the complexity and increase in size worth this capability?		This algorithm provides the ability to encode anything such as Unicode, pictures, or anything else under the sun. Is the complexity and increase in size worth this capability?

-	==~~Proposed barcode~~==	+	==Barcode scheme to encode text only==
-		+
-	~~<font color="red">'''Feedback more than welcome!'''</font>~~	+

	===Case-sensitive codon tables===		===Case-sensitive codon tables===

Austin J. Che: /* Alternative barcode */

Austin J. Che — Mon, 06 Feb 2006 21:41:11 GMT

Alternative barcode

←Older revision		Revision as of 21:41, 6 February 2006
Line 6:		Line 6:

	Compression algorithms for DNA sequences: X. Chen, S. Kwong, M. Li, Genome Informatics (GIW'99), Tokyo, Japan, pp.51-61, 1999.		Compression algorithms for DNA sequences: X. Chen, S. Kwong, M. Li, Genome Informatics (GIW'99), Tokyo, Japan, pp.51-61, 1999.
		+
		+
		+	I've put up a test page for playing with encoding binary into DNA at http://synbio.mit.edu/tools/encoder.cgi
		+
		+	The general encoding/decoding method: Each byte of 8 bits is split into 4x2 bits. Each pair of bits at each location is mapped to some nucleotide. For example 00 at position 0 could be mapped to A, 01 at position 1 to T, 00 at position 1 to T, etc. To be decodable, there must be a 1 to 1 mapping at each position from 2 bits to 4 nucleotides. But this leaves <math>24^4</math> different ways to do this type of encoding. Currently, I pick a particular encoding that for some common things that Reshma would like to encode (plasmid names, parts, etc. in ASCII) have the following properties:
		+	* %GC close to 50%
		+	* %GT as high as possible (biased nucleotide use).
		+
		+	Biasing the nucleotides makes it less likely for restriction sites or other secondary structures to appear. In addition, it allows for an easier choice of an escape sequence. The idea is to have a family of escape sequences, for example ACNNNAC, which can be inserted anywhere you want. This allows you to modify the %GC content if desired, break up bad sequences, or whatever else by inserting arbitrary non-coding sequence. If the escape occurs in the real sequence, it gets escaped itself. Escapes have not been chosen or implemented yet.
		+
		+	Another idea I had was to try all possible encodings and pick the one that provided the best properties that one wants. At the beginning (as the start code), we print the encoding (would take a fixed 12nt).
		+
		+	Randy suggested some form of compression. Not sure how much space we save or how much more complex it would make the algorithm.
		+
		+	This algorithm provides the ability to encode anything such as Unicode, pictures, or anything else under the sun. Is the complexity and increase in size worth this capability?

	==Proposed barcode==		==Proposed barcode==

Reshma P. Shetty at 18:28, 4 February 2006

Reshma P. Shetty — Sat, 04 Feb 2006 18:28:38 GMT

←Older revision		Revision as of 18:28, 4 February 2006
Line 1:		Line 1:
	==Alternative barcode==		==Alternative barcode==

-	~~Actually encode a~~ bit ~~string~~ into ~~the~~ DNA (Tom and Austin).	+	Enable encoding of arbitrary bit strings into DNA without introducing "biologically bad" sequences. (Tom and Austin).
		+
		+	[http://www.roubaixinteractive.com/PlayGround/Binary_Conversion/Binary_To_Text.asp Text to bit string converter] (ASCII not Unicode)
		+
		+	Compression algorithms for DNA sequences: X. Chen, S. Kwong, M. Li, Genome Informatics (GIW'99), Tokyo, Japan, pp.51-61, 1999.

	==Proposed barcode==		==Proposed barcode==