Waterloo

From 2007.igem.org

(Difference between revisions)
(Half-Adder vs Full-Adder)
 
(167 intermediate revisions not shown)
Line 1: Line 1:
-
<center><font size="6">[[Image:UWLogo.jpg]] University of Waterloo iGEM Team </font></center>
+
<center> [[Image:UW_iGEMLogoHeader.png | 935px]] </center>
 +
<br>
-
== Our Team ==
+
{| style="border-spacing:0px; border-width:thin; border-color:black; border-style:solid"
-
The UW iGEM team is a very interdisciplinary group. Our team members span the three faculties of Science, Mathematics and Engineering and include the programs of Biology, Biomedical Sciences, Computer Science, Bioinformatics, Computer Engineering, Electrical Engineering, Chemical Engineering, and Mathematical Physics at undergraduate and graduate levels. Even our professor advisors are cross-appointed to two other faculties. Our diverse backgrounds bring together a wide range of skills and ideas to the iGEM project. iGEM is giving us the opportunity to apply the skills learned in our lectures and labs to real life applications in molecular biology and biotechnology.
+
|-
 +
| style="font-size:x-large; font-weight:bold; border-bottom-width:thin; border-bottom-color:black; border-bottom-style:solid; font-size:x-large; font-weight:bold; padding:5px; background-color:#FBCC30" | Our Team
 +
|-
 +
| style="padding:5px" | [[Image:Group photo mimi1.JPG|470px|left|thumb|Undergraduate Members]]  [[Image:UW_Advisors.jpg|407px|center|thumb|Faculty and Graduate Advisors]]
 +
|-
 +
| style="padding:5px" | The UW iGEM team is a very interdisciplinary group. Our team members span three faculties: Science, Mathematics, and Engineering, and represent a wide range of undergraduate programs: Biology, Biomedical Sciences, Biochemistry, Computer Science, Bioinformatics, Computer Engineering, Electrical Engineering, Chemical Engineering, Systems Design Engineering, and Mathematical Physics.
-
==Abstract==
+
Drawing on our diverse backgrounds, we bring a wide range of skills and modes of creative thinking to our iGEM project. The iGEM competition is providing us with an opportunity to become more familiar with the emerging field of synthetic biology in an engaging and fun atmosphere.  In addition to gaining experience in the design, construction, and analysis of genetic circuits, we are also meeting the challenge of bringing together a large, diverse group toward a common goal.
-
==Background==
+
-
===Binary Addition===
+
-
When working in binary, only two digits are used: 0 and 1. Counting therefore proceeds as:
+
-
# 1
+
|}
-
# 10
+
-
# 11
+
-
# 100
+
-
# 101
+
-
# 111
+
-
etc.
+
-
To add two binary numbers, the process is much the same as adding two decimal (ordinary) numbers, except that instead of carrying when two digits add to ten, carrying must be performed when two digits add to two. In other words, 0 + 1 adds to 1, but 1 + 1 adds to 0 with a carry of 1, which gives 10 (just as in decimal 1 + 9 would add to 0 with a carry of 1, to give 10). A complete list of the possibilities is as follows:
+
<br clear="all">
-
[[Image:000.jpg]]
+
{| style="border-spacing:0px; border-width:thin; border-color:black; border-style:solid; width:100%"
 +
|-
 +
| colspan="4" style="border-bottom-width:thin; border-bottom-color:black; border-bottom-style:solid; font-size:x-large; font-weight:bold; padding:5px; background-color:#FBCC30" | Our Project
 +
|-
 +
| colspan="4" style="padding:5px; font-size:large" | Abstract
 +
|-
 +
| colspan="2" style="vertical-align:top; border-bottom-width:thin; border-bottom-color:black; border-bottom-style:solid; padding:5px" | The goal of this project is to design a basic device for computing. Our idea was to reproduce a circuit element called a half adder with DNA, which takes in two 1-bit inputs, adds them, and outputs a sum and a carry. Our device responds to two inputs: red light and the chemical tetracycline. The input sensors control a set of genetic switches in order to carry out the computation and fluoresces green, red, or neither, depending on the outcome.
-
===Half-Adder vs Full-Adder===
+
Half adders are used as building blocks for full adders, which perform calculations similar to long addition but in binary. They are also an essential component in a device called the Arithmetic Logic Unit (ALU), a fundamental building block for the central processing unit in a modern computer. ALUs perform simple and complex operations such as bitwise logical operations and mathematical operations.  
-
Any construct designed to add two numbers will either be a half-adder or a full-adder. A half-adder can only add together two single digits, whereas a full-adder is needed to add two numbers of any length greater than one digit.
+
-
For example, a half-adder could perform the addition 1 + 0 = 1, or 1 + 1 = 10, but it would take a full-adder to be able to perform 1100101 + 100101.
+
The constructs for the half adder were built in parallel as well as the testing constructs. A future extension to this project would be to create a full adder. More information on each stage of the project is available below.
-
In terms of implementation, a half-adder accepts two inputs (the two digits to be summed) and returns two outputs (the "sum bit" and the "carry bit"). To add 1 + 1, the two inputs would each be 1, the sum bit would be 0, and the carry bit would be 1. A full list of the possibilities is shown in Figure 1.
+
| colspan="2" style="border-bottom-width:thin; border-bottom-color:black; border-bottom-style:solid; padding:5px; vertical-align:middle" | [[Image:Design schematic.jpg|thumb|center|475px|Schematic Design of the Biological Half-Adder]]
 +
|-
 +
| style="width:25%; border-right-width:thin; border-right-color:black; border-right-style:solid; font-size:large; text-align:left; padding:5px; background-color:#FBCC30" | [[Project | Project Design]] || style="width:25%; border-right-width:thin; border-right-color:black; border-right-style:solid; font-size:large; text-align:left; padding:5px; background-color:#FBCC30"  | [[Modelling | Mathematical Modelling]] || style="width:25%; border-right-width:thin; border-right-color:black; border-right-style:solid; font-size:large; text-align:left; padding:5px; background-color:#FBCC30" | [[Construction_and_Testing | Construction and Testing]] || style="width:25%; font-size:large; text-align:left; padding:5px; background-color:#FBCC30" | [[Future_Work | Future Work]]
 +
|-
 +
| style="vertical-align:top; border-right-width:thin; border-right-color:black; border-right-style:solid; padding:5px" |
 +
* Binary addition and boolean logic
 +
* Half-adder vs. full-adder designs
 +
* Biological half-adder implementation
 +
| style="vertical-align:top; border-right-width:thin; border-right-color:black; border-right-style:solid; padding:5px" |
 +
* Modelling the gene regulatory network
 +
* Simulation results
 +
| style="vertical-align:top; border-right-width:thin; border-right-color:black; border-right-style:solid; padding:5px" |
 +
* Strategy for half-adder construction
 +
* Testing constructs for device
 +
* Test execution plan
 +
* Submitted parts
 +
| style="vertical-align:top; padding:5px" |
 +
* Explanation of a full adder
 +
* Gene design for full adder
 +
* Implementation plan
 +
|}
-
A full-adder is merely a half-adder that accepts an extra input; namely, the carry bit from another full-adder. Each full-adder is responsible for adding one pair of corresponding digits from the two numbers to be added, ''and'' it must add to that the carry bit from the previous full-adder. The full-adder will output the resulting sum bit and carry bit, and the process will continue until all the digits have been added. Such a chain of full-adders is called a ripple carry adder. See Figure 2 for a full list of possibilities.
+
<br clear="all">
 +
{| style="border-spacing:0px; border-width:thin; border-color:black; border-style:solid; width:100%; text-align:center"
 +
|-
 +
| style="font-size:x-large; font-weight:bold; font-size:x-large; font-weight:bold; padding:5px; background-color:#FBCC30; border-bottom-width:thin; border-bottom-color:black; border-bottom-style:solid; text-align:left" colspan="15" | Acknowledgements
 +
|-
 +
| colspan="3" | [[Image:Fsf_logo.gif|150px]] || colspan="3" | [[Image:MEF_logo.gif|150px]] || colspan="3" | [[Image:SFF_Logo.gif|150px]] || colspan="3" | [[Image:WEEFLogo.jpg|150px]] || colspan="3" | [[Image:WatSEF_Logo.jpg|150px]]
 +
|-
 +
| colspan="3" | [http://www.science.uwaterloo.ca/fsf/index.html Faculty of Science Foundation ] || colspan="3" | [http://www.student.math.uwaterloo.ca/~mefcom/ Mathematics Endowment Fund ] || colspan="3" | [http://www.eng.uwaterloo.ca/~sff/ Sir Sanford Fleming Foundation] || colspan="3" | [http://www.weef.uwaterloo.ca/ Waterloo Engineering Endowment Fund] || colspan="3" | [http://www.science.uwaterloo.ca/~watsef/mainpage.html Waterloo Science Endowment Fund]
 +
|-
 +
| colspan="15" | &nbsp;
 +
|-
 +
| colspan="5" | [[Image:UW_EngFacLogo.PNG |150px]] || colspan="5" | [[Image:UW_SciFacLogo.PNG|150px]] || colspan="5" | [[Image:UW_MathFacLogo.PNG|150px]]
 +
|-
 +
| colspan="5" | [http://www.engineering.uwaterloo.ca University of Waterloo Faculty of Engineering] || colspan="5" | [http://www.science.uwaterloo.ca University of Waterloo Faculty of Science] || colspan="5" | [http://www.math.uwaterloo.ca University of Waterloo Faculty of Mathematics]
 +
|-
 +
| colspan="15" | &nbsp;
 +
|-
 +
| colspan="5" style="padding:5px" | [[Image:UW_Waterloocrest.PNG | 150px]] || colspan="10" style="text-align:left; padding:5px" | We would like to thank the following people for their support and guidance:
 +
* Dr. Trevor Charles
 +
* Dr. Barbara Moffatt
 +
* Dr. Joshua Neufeld
 +
|}
-
''Figure 1: Half Adder Truth Table''
+
<br clear="all">
-
 
+
<center>
-
[[Image:111.jpg|thumb|Figure 1: Half-Adder Truth Table]]
+
  [[Waterloo | Home ]] | [[Project | Project]] | [[Modelling | Mathematical Modelling]] | [[Construction_and_Testing | Construction and Testing]] | [[Future_Work | Future Work]]  
-
 
+
</center>
-
 
+
-
''Figure 2: Full Adder Truth Table''
+
-
 
+
-
[[Image:333.jpg]]
+
-
 
+
-
 
+
-
''Figure 3: Long Addition of 101 + 001''
+
-
 
+
-
[[Image:222.jpg]]
+
-
 
+
-
===Logic Gates and Implementing an Adder===
+
-
A '''logic gate''' is a device that accepts two binary input(s) (each a 0 or 1) and returns one binary output. A list of relevant logic gates is as follows:
+
-
 
+
-
# OR gate
+
-
# XOR gate
+
-
# AND gate
+
-
# NOT gate
+
-
 
+
-
For the following explanations, A and B represent statements that can be either true or false.
+
-
 
+
-
 
+
-
====OR Gate====
+
-
 
+
-
Consider the statement "A OR B". If either A or B is true, the statement is said to be true. The only time this statement will be false is if both A and B are false. This is the meaning of the OR operation.
+
-
 
+
-
An OR gate accepts two binary inputs, where a 1 to represents "true" and a 0 represents "false". The output of the OR gate is also binary, and similarly represents either "true" or "false".
+
-
 
+
-
To illustrate,
+
-
 
+
-
0 OR 0 = 0
+
-
1 OR 0 = 0 OR 1 = 1
+
-
1 OR 1 = 1
+
-
 
+
-
 
+
-
====XOR Gate====
+
-
 
+
-
XOR is an abbreviation for "exclusive OR". The XOR gate is similar to the OR gate, the only difference being that it will return false if both inputs are true.
+
-
 
+
-
For example,
+
-
 
+
-
1 XOR 0 = 1
+
-
1 XOR 1 = 0
+
-
 
+
-
 
+
-
====AND gate====
+
-
 
+
-
The AND gate will return 1 (true) '''only if both the inputs are 1 (true)'''. Otherwise, it will return a 0.
+
-
 
+
-
To illustrate,
+
-
 
+
-
0 AND 0 = 0
+
-
1 AND 0 = 0 AND 1 = 0
+
-
1 AND 1 = 1
+
-
 
+
-
 
+
-
====NOT gate====
+
-
 
+
-
The NOT gate accepts one input, and simply switches its value.
+
-
 
+
-
NOT 1 = 0
+
-
NOT 0 = 1
+
-
 
+
-
 
+
-
====Using logic gates to make an adder====
+
-
 
+
-
Given two binary inputs A and B, their sum can be computed by passing these inputs through various logic gates. The process is illustrated in Figures 4 and 5.
+
-
 
+
-
===DNA as Logic Gates===
+
-
The crux of our project is the idea of using DNA as logic gates.
+
-
 
+
-
==Project Details==
+
-
===Inputs (stimuli and the genes used to detect them)===
+
-
===Output (observable change and what it represents)===
+
-
===Gene Diagram===
+
-
 
+
-
==Testing/Results==
+
-
===Mathematical Model===
+
-
===Measurements===
+
-
 
+
-
==Extensions==
+
-
===Full Adder===
+
-
 
+
-
==Acknowledgements== (Sponsor logos)
+

Latest revision as of 04:02, 27 October 2007

UW iGEMLogoHeader.png


Our Team
Undergraduate Members
Faculty and Graduate Advisors
The UW iGEM team is a very interdisciplinary group. Our team members span three faculties: Science, Mathematics, and Engineering, and represent a wide range of undergraduate programs: Biology, Biomedical Sciences, Biochemistry, Computer Science, Bioinformatics, Computer Engineering, Electrical Engineering, Chemical Engineering, Systems Design Engineering, and Mathematical Physics.

Drawing on our diverse backgrounds, we bring a wide range of skills and modes of creative thinking to our iGEM project. The iGEM competition is providing us with an opportunity to become more familiar with the emerging field of synthetic biology in an engaging and fun atmosphere. In addition to gaining experience in the design, construction, and analysis of genetic circuits, we are also meeting the challenge of bringing together a large, diverse group toward a common goal.


Our Project
Abstract
The goal of this project is to design a basic device for computing. Our idea was to reproduce a circuit element called a half adder with DNA, which takes in two 1-bit inputs, adds them, and outputs a sum and a carry. Our device responds to two inputs: red light and the chemical tetracycline. The input sensors control a set of genetic switches in order to carry out the computation and fluoresces green, red, or neither, depending on the outcome.

Half adders are used as building blocks for full adders, which perform calculations similar to long addition but in binary. They are also an essential component in a device called the Arithmetic Logic Unit (ALU), a fundamental building block for the central processing unit in a modern computer. ALUs perform simple and complex operations such as bitwise logical operations and mathematical operations.

The constructs for the half adder were built in parallel as well as the testing constructs. A future extension to this project would be to create a full adder. More information on each stage of the project is available below.

Schematic Design of the Biological Half-Adder
Project Design Mathematical Modelling Construction and Testing Future Work
  • Binary addition and boolean logic
  • Half-adder vs. full-adder designs
  • Biological half-adder implementation
  • Modelling the gene regulatory network
  • Simulation results
  • Strategy for half-adder construction
  • Testing constructs for device
  • Test execution plan
  • Submitted parts
  • Explanation of a full adder
  • Gene design for full adder
  • Implementation plan


Acknowledgements
Fsf logo.gif MEF logo.gif SFF Logo.gif WEEFLogo.jpg WatSEF Logo.jpg
[http://www.science.uwaterloo.ca/fsf/index.html Faculty of Science Foundation ] [http://www.student.math.uwaterloo.ca/~mefcom/ Mathematics Endowment Fund ] [http://www.eng.uwaterloo.ca/~sff/ Sir Sanford Fleming Foundation] [http://www.weef.uwaterloo.ca/ Waterloo Engineering Endowment Fund] [http://www.science.uwaterloo.ca/~watsef/mainpage.html Waterloo Science Endowment Fund]
 
UW EngFacLogo.PNG UW SciFacLogo.PNG UW MathFacLogo.PNG
[http://www.engineering.uwaterloo.ca University of Waterloo Faculty of Engineering] [http://www.science.uwaterloo.ca University of Waterloo Faculty of Science] [http://www.math.uwaterloo.ca University of Waterloo Faculty of Mathematics]
 
UW Waterloocrest.PNG We would like to thank the following people for their support and guidance:
  • Dr. Trevor Charles
  • Dr. Barbara Moffatt
  • Dr. Joshua Neufeld


  Home  |  Project |  Mathematical Modelling |  Construction and Testing |  Future Work