'Bacterial Computers': Genetically Engineered Bacteria Have Potential To Solve Complicated Mathematical Problems

SOURCE

ScienceDaily (July 24, 2009) — US researchers have created 'bacterial computers' with the potential to solve complicated mathematics problems. The findings of the research demonstrate that computing in living cells is feasible, opening the door to a number of applications. The second-generation bacterial computers illustrate the feasibility of extending the approach to other computationally challenging math problems.

A research team made up of four faculty members and 15 undergraduate students from the biology and mathematics departments at Missouri Western State University in Missouri and Davidson College in North Carolina, USA engineered the DNA of Escherichia coli bacteria, creating bacterial computers capable of solving a classic mathematical problem known as the Hamiltonian Path Problem.
The research extends previous work published last year in the same journal to produce bacterial computers that could solve the Burnt Pancake Problem.
The Hamiltonian Path Problem asks whether there is a route in a network from a beginning node to an ending node, visiting each node exactly once. The student and faculty researchers modified the genetic circuitry of the bacteria to enable them to find a Hamiltonian path in a three-node graph. Bacteria that successfully solved the problem reported their success by fluorescing both red and green, resulting in yellow colonies.
Synthetic biology is the use of molecular biology techniques, engineering principles, and mathematical modeling to design and construct genetic circuits that enable living cells to carry out novel functions. "Our research contributed more than 60 parts to the Registry of Standard Biological Parts, which are available for use by the larger synthetic biology community, including the newly split red fluorescent protein and green fluorescent protein genes," said Jordan Baumgardner, recent graduate of Missouri Western and first author of the research paper. "The research provides yet another example of how powerful and dynamic synthetic biology can be. We used synthetic biology to solve mathematical problems; others find applications in medicine, energy and the environment. Synthetic biology has great potential in the real world."
According to Dr. Eckdahl, the corresponding author of the article, synthetic biology affords a new opportunity for multidisciplinary undergraduate research training. "We have found synthetic biology to be an excellent way to engage students in research that connects biology and mathematics. Our students learn firsthand the value of crossing traditional disciplinary lines."
Journal references:
Jordan Baumgardner, Karen Acker, Oyinade Adefuye, Samuel THOMAS Crowley, Will DeLoache, James O Dickson, Lane Heard, Andrew T Martens, Nickolaus Morton, Michelle Ritter, Amber Shoecraft, Jessica Treece, Matthew Unzicker, Amanda Valencia, Mike Waters, A. M. Campbell, Laurie J. Heyer, Jeffrey L. Poet and Todd T. Eckdahl. Solving a Hamiltonian Path Problem with a bacterial computer. Journal of Biological Engineering, (in press) [link]
Haynes et al. Engineering bacteria to solve the Burnt Pancake Problem. Journal of Biological Engineering, 2008; 2 (1): 8 DOI: 10.1186/1754-1611-2-8
Adapted from materials provided by BioMed Central, via EurekAlert!, a service of AAAS.

DNA Sudoku: Logic Of 'Sudoku' Math Puzzle Used To Vastly Enhance Genome-sequencing Capability

SOURCE

ScienceDaily (June 25, 2009) — A math-based game that has taken the world by storm with its ability to delight and puzzle may now be poised to revolutionize the fast-changing world of genome sequencing and the field of medical genetics, suggests a new report by a team of scientists at Cold Spring Harbor Laboratory (CSHL). The report will be published as the cover story in the July 1st issue of the journal Genome Research.

Combining a 2,000-year-old Chinese math theorem with concepts from cryptology, the CSHL scientists have devised "DNA Sudoku." The strategy allows tens of thousands of DNA samples to be combined, and their sequences – the order in which the letters of the DNA alphabet (A, T, G, and C) line up in the genome – to be determined all at once.
This achievement is in stark contrast to past approaches that allowed only a single DNA sample to be sequenced at a time. It also significantly improves upon current approaches that, at best, can combine hundreds of samples for sequencing.
"In theory, it is possible to use the Sudoku method to sequence more than a hundred thousand DNA samples," says CSHL Professor Gregory Hannon, Ph.D., a genomics expert and leader of the team that invented the "Sudoku" approach. At that level of efficiency, it promises to reduce costs dramatically. A sequencing project that costs upwards of $10 million using conventional methods may be accomplished for $50,000 to $80,000 using DNA Sudoku, he estimates.
Originally devised to overcome a sequencing limitation that dogged one of the Hannon lab's research projects, the new method has tremendous potential for clinical applications. It can be used, says Hannon, to analyze specific regions of the genomes of a large population and identify individuals who carry mutations that cause genetic diseases – a process known as genotyping.
The CSHL team has already begun to explore this possibility via a collaboration with Dor Yeshorim, a New York-based organization that has collected DNA from thousands of members of orthodox Jewish communities. The organization's aim is to prevent genetic diseases such as Tay-Sachs or cystic fibrosis that occur frequently within specific ethnic populations. The team's new method will now allow the many thousands of DNA samples gathered by Dor Yeshorim to be processed and sequenced in a single time-saving and cost-effective experiment, which should identify individuals who carry disease-causing mutations.
The advantages of DNA Sudoku
The mixing together and simultaneous sequencing of a massive number of DNA samples is known as multiplexing. In previous multiplexing approaches, scientists first tagged each sample with a barcode – a short string of DNA letters known as oligonucleotides – before mixing it with other samples that also had unique tags. After the sample mix had been sequenced, scientists could use the barcode tags on the resulting sequences as identification markers and thus tell which sequence belonged to which sample.
"But this approach is very limiting," explains Yaniv Erlich, a graduate student in the Hannon laboratory and first author on the "DNA Sudoku" paper. "It's time-consuming and costly to have to design a unique barcode for each sample prior to sequencing, especially if the number of samples runs in the thousands."
In order to circumvent this limitation, Erlich and others in the Hannon lab came up with the idea of mixing the samples in specific patterns, thereby creating pools of samples. And instead of tagging the individual samples within each pool, the scientists tagged each pool as a whole with one barcode. "Since we know which pool contains which samples, we can link a sequence to an individual sample with high confidence," says Erlich.
The key to the team's innovation is the pooling strategy, which is based on the 2,000-year-old Chinese remainder theorem. "It minimizes the number of pools and the amount of sequencing," says Hannon of their method, which they dubbed "DNA Sudoku" because of its similarity to the logic and combinatorial number-placement rules used in the popular game.
The method, which the CSHL team has patented, is currently best suited for genotype analyses that require only short segments of an individual's genome to be sequenced to find out if the individual is carrying a certain variant of a gene or a rare mutation. But as sequencing technologies improve and researchers gain the ability to generate sequences for longer segments of the genome, Hannon envisions wider clinical applications for their method such as HLA typing, already an important diagnostic tool for autoimmune diseases, cancer, and for predicting the risk of organ transplantation.
Journal reference:
Erlich et al. DNA Sudoku--harnessing high-throughput sequencing for multiplexed specimen analysis. Genome Research, 2009; DOI: 10.1101/gr.092957.109
Adapted from materials provided by Cold Spring Harbor Laboratory, via EurekAlert!, a service of AAAS.

New Pattern Found in Prime Numbers

SOURCE

(PhysOrg.com) -- Prime numbers have intrigued curious thinkers for centuries. On one hand, prime numbers seem to be randomly distributed among the natural numbers with no other law than that of chance. But on the other hand, the global distribution of primes reveals a remarkably smooth regularity. This combination of randomness and regularity has motivated researchers to search for patterns in the distribution of primes that may eventually shed light on their ultimate nature.

In a recent study, Bartolo Luque and Lucas Lacasa of the Universidad Politécnica de Madrid in Spain have discovered a new pattern in primes that has surprisingly gone unnoticed until now. They found that the distribution of the leading digit in the prime number sequence can be described by a generalization of Benford’s law. In addition, this same pattern also appears in another number sequence, that of the leading digits of nontrivial Riemann zeta zeros, which is known to be related to the distribution of primes. Besides providing insight into the nature of primes, the finding could also have applications in areas such as fraud detection and stock market analysis.
“Mathematicians have studied prime numbers for centuries,” Lacasa told PhysOrg.com. “New insights and concepts coming from nonlinear science, such as multiplicative processes, help us to look at prime numbers from a different perspective. According to this focus, it becomes significant that even today it is still possible to discover unnoticed hints of statistical regularity in such sequences, without being an expert in number theory. However, the most significant issue in this work is not to unveil this pattern in primes and Riemann zeros, but to understand the reason and implications of such unexpected structure, not just for number theoretical issues but, interestingly, for other disciplines as well. For instance, these results deepen our understanding of correlations in systems composed of many elements.”
Benford’s law (BL), named after physicist Frank Benford in 1938, describes the distribution of the leading digits of the numbers in a wide variety of data sets and mathematical sequences. Somewhat unexpectedly, the leading digits aren’t randomly or uniformly distributed, but instead their distribution is logarithmic. That is, 1 as a first digit appears about 30% of the time, and the following digits appear with lower and lower frequency, with 9 appearing the least often. Benford’s law has been shown to describe disparate data sets, from physical constants to the length of the world’s rivers.
Since the late ‘70s, researchers have known that prime numbers themselves, when taken in very large data sets, are not distributed according to Benford’s law. Instead, the first digit distribution of primes seems to be approximately uniform. However, as Luque and Lacasa point out, smaller data sets (intervals) of primes exhibit a clear bias in first digit distribution. The researchers noticed another pattern: the larger the data set of primes they analyzed, the more closely the first digit distribution approached uniformity. In light of this, the researchers wondered if there existed any pattern underlying the trend toward uniformity as the prime interval increases to infinity.

The set of all primes - like the set of all integers - is infinite. From a statistical point of view, one difficulty in this kind of analysis is deciding how to choose at “random” in an infinite data set. So a finite interval must be chosen, even if it is not possible to do so completely randomly in a way that satisfies the laws of probability. To overcome this point, the researchers decided to chose several intervals of the shape [1, 10d]; for example, 1-100,000 for d = 5, etc. In these sets, all first digits are equally probable a priori. So if a pattern emerges in the first digit of primes in a set, it would reveal something about first digit distribution of primes, if only within that set.
By looking at multiple sets as d increases, Luque and Lacasa could investigate how the first digit distribution of primes changes as the data set increases. They found that primes follow a size-dependent Generalized Benford’s law (GBL). A GBL describes the first digit distribution of numbers in series that are generated by power law distributions, such as [1, 10d]. As d increases, the first digit distribution of primes becomes more uniform, following a trend described by GBL. As Lacasa explained, both BL and GBL apply to many processes in nature.
“Imagine that you have $1,000 in your bank account, with an interest rate of 1% per month,” Lacasa said. “The first month, your money will become $1,000*1.01 = $1,010. The next month, $1,010*1.01, and so on. After n months, you will have $1,000*(1.01)^n. Notice that you will need many months to go from $1,000 to $2,000, while to go from $8,000 to $9,000 will be much easier. When you analyze your accounting data, you will realize that the first digit 1 is more represented than 8 or 9, precisely as Benford's law dictates. This is a very basic example of a multiplicative process where 0.01 is the multiplicative constant.
“Physicists have shown that many processes in nature can be modeled as stochastic multiplicative processes, where the previously constant value of 0.01 is now a random variable and the data equivalent to the money of our latter example is another random variable with an underlying distribution 1/x. Stochastic processes with such distributions are shown to follow BL. Now, many other phenomena fit better to a stochastic process with a more general underlying probability x^[-alpha], where alpha is different from one. The first digit distribution related with this general power law distribution is the so-called Generalized Benford law (which converges to BL for alpha = 1).”
Significantly, Luque and Lacasa showed in their study that GBL can be explained by the prime number theorem; specifically, the shape of the mean local density of the sequences is responsible for the pattern. The researchers also developed a mathematical framework that provides conditions for any distribution to conform to a GBL. The conditions build on previous research, which has shown that Benford behavior could occur when a distribution follows BL for particular values of its parameters, as in the case of primes. Luque and Lacasa also investigated the sequence of nontrivial Riemann zeta zeros, which are related to the distribution of primes, and whose distribution of the zeros is considered to be one of the most important unsolved mathematical problems. Although the distribution of the zeros does not follow BL, here the researchers found that it does follow a size-dependent GBL, as in the case of the primes.
The researchers suggest that this work could have several applications, such as identifying other sequences that aren’t Benford distributed, but may be GBL. In addition, many applications that have been developed for Benford’s law could eventually be generalized to the wider context of the Generalized Benford’s law. One such application is fraud detection: while naturally generated data obey Benford’s law, randomly guessed (fraudulent) data do not, in general.
“BL is a specific case of GBL,” Lacasa explained. “Many processes in nature can be fitted to a GBL with alpha = 1, i.e. a BL. The hidden structure that Benford's law quantifies is lost when numbers are artificially modified: this is a principle for fraud detection in accounting, where the combinatorial mechanisms associated to accounting sets are such that BL applies. The same principle holds for processes following GBL with a generic alpha, where BL fails. Last, for processes whose underlying density is not x^(-alpha) but 1/logN, a size-dependent GBL would be the correct hallmark.”
More information: Bartolo Luque and Lucas Lacasa. “The first digit frequencies of primes and Riemann zeta zeros.” Proceedings of the Royal Society A. doi: 10.1098/rspa.2009.0126.

Way To Control Chaos? Rigid Structure Discovered In Center Of Air Turbulence

SOURCE

ScienceDaily (May 6, 2009) — Pioneering mathematical engineers have discovered for the first time a rigid structure which exists within the centre of turbulence, leading to hope that its chaotic movement could be controlled in the future.

Dr Sotos Generalis from Aston University in Birmingham, UK and Dr Tomoaki Itano from Kansai University in Osaka, Japan, believe their discovery of the Hairpin Vortex Solution could revolutionise our understanding of turbulence and our ability to control it.
This rigid, set structure, named after its hairpin like shape was found within Plane Couette flow. This is a prototype of turbulent shear flow, where turbulence is created in fluid flow between the space of two opposite moving planar fluid boundaries, when high- and low-speed fluids collide.
Everyone from Formula One drivers experiencing drag, through to aeroplane passengers suffering a bumpy flight, will have experienced clear-air turbulence, the mixing of high- and low-speed air in the atmosphere.
This newly found turbulent state is constituted by a number of elements found in a coherent flow structure and has been described by the research team as a "tapestry of knotted vortices."
While structures, known as wall structures have been found on the ‘edge’ of turbulence, an elusive middle or wake structure has never been discovered, until now.
Dr Generalis believes that finding a regimented structure within the very heart of Couette flow could prove invaluable to controlling turbulence and the effects of turbulence between two moving boundaries, in the future. This could include working machinery parts, medical treatment involving blood flow, and turbulence in air, sea and road travel.
“Ten years ago scientists believed turbulence was in a ‘world’ of its own, until we began to find ‘wall structures’ on its side. We believed a middle or wake structure might exist, and now we can prove there is regimented structure at the very centre of turbulence. This new discovery paves the way for the ‘marriage’ between wake and wall structures in shear flow turbulence and provides a unique picture of the Couette flow turbulent eddies only observed but never understood before.
The team’s findings of this missing central link have been published in Physical Review Letters and come after nearly five years of research, created by thousands of computer generated shear flow models. The result was obtained by replicating the exposure of two opposite plates to hot and cold conditions, moving from a static to dynamic position. The research team are now aiming to find if similar structures exist within other cases of turbulent fluid flow.
“The hairpins expose an all new ‘view’ of the transition to turbulence and it is our aim to ‘unify’ this idea discovered in Couette flow, into other areas of shear flow in general,” added Dr Generalis.
Journal reference:
Tomoaki Itano and Sotos C. Generalis. Hairpin Vortex Solution in Planar Couette Flow: A Tapestry of Knotted Vortices. Physical Review Letters, 2009; 102 (11): 114501 DOI: 10.1103/PhysRevLett.102.114501
Adapted from materials provided by Aston University.

New Mathematical System Helps To Cut Bus Journey Times

SOURCE

ScienceDaily (Mar. 17, 2009) — A research team from the University of Burgos (UBU) has designed a system to reduce the time spent waiting at bus stops in the city, as well as the length of bus journeys. The method, which could be applied to other locations, is based on a mathematical strategy known as “taboo search.”

The UBU’s Research Group on Metaheuristic Techniques, working with Mexican researchers, has come up with a system to reduce the time spent waiting at bus stops in Burgos from 20 to 17 minutes, and to cut average bus journey times from 16 to 13.5 minutes.
“This translates into a 13% performance improvement of this urban transport service,” Joaquín A. Pacheco, the research group’s coordinator and director of the UBU’s Applied Economics Department, tells SINC.
“When we face a problem of this kind, we can use an exact method, which gives us an optimal solution but takes a long time to calculate – or we can use an approximate or heuristic technique, which provides a good solution with less calculation time,” says Pacheco, who chose the second method.
Heuristic algorithms are more effective in certain situations, such as when the data for a problem to be solved are imprecise, or when fast and adaptable solutions are needed. The researchers used the “taboo search” method from the most highly perfected heuristic techniques, known as metaheuristics. This strategy uses learning methods, and classifies certain options as “forbidden” or “taboo”, to avoid developing solutions that have already been previously created.
“For example, when searching for solutions, if a bus has just left a particular stop, this stop is then marked as ‘taboo’ and it cannot be included as part of that route again for a certain number of iterations (repetitions),” explains Pacheco.
The results of the “taboo search” made it possible to design slight modifications to the current lines operating in the city, for example by making a bus route run along one street instead of another, or by eliminating some twists and turns, as well as to redistribute the bus fleet, especially in the eastern part of the city. These improvements will allow urban transport users in Burgos to save time during their trips.
In order to carry out this study, the researchers maintained a set number of bus routes, as well as their starting and finishing points. The work was commissioned by Burgos City Council, which requested that no abrupt changes be made to the service. The city has 382 bus stops served by 24 routes operating on working days.
This method can also be used in other towns, according to its developers. The metaheuristic techniques are already being applied in Castilla-La Mancha and the Balearic Islands in order to reduce the cost of school transport services, and the amount of time students have to wait at bus stops.
Journal reference:
Joaquín Pacheco, Ada Álvarez, Silvia Casado, José Luis González-Velarde. A tabu search approach to an urban transport problem in northern Spain. Computers & Operations Research, 2009; 36 (3): 967 DOI: 10.1016/j.cor.2007.12.002
Adapted from materials provided by Plataforma SINC, via AlphaGalileo.