Month: June 2015

Comparing the genomes of different species—or different members of the same species—is the basis of a great deal of modern biology. DNA sequences that are conserved across species are likely to be functionally important, while variations between members of the same species can indicate different susceptibilities to disease.

The basic algorithm for determining how much two sequences of symbols have in common—the “edit distance” between them—is now more than 40 years old. And for more than 40 years, computer science researchers have been trying to improve upon it, without much success.
At the ACM Symposium on Theory of Computing (STOC) next week, MIT researchers will report that, in all likelihood, that’s because the algorithm is as good as it gets. If a widely held assumption about computational complexity is correct, then the problem of measuring the difference between two genomes—or texts, or speech samples, or anything else that can be represented as a string of symbols—can’t be solved more efficiently.
In a sense, that’s disappointing, since a computer running the existing algorithm would take 1,000 years to exhaustively compare two human genomes. But it also means that computer scientists can stop agonizing about whether they can do better.
“This edit distance is something that I’ve been trying to get better algorithms for since I was a graduate student, in the mid-’90s,” says Piotr Indyk, a professor of computer science and engineering at MIT and a co-author of the STOC paper. “I certainly spent lots of late nights on that—without any progress whatsoever. So at least now there’s a feeling of closure. The problem can be put to sleep.”
Moreover, Indyk says, even though the paper hasn’t officially been presented yet, it’s already spawned two follow-up papers, which apply its approach to related problems. “There is a technical aspect of this paper, a certain gadget construction, that turns out to be very useful for other purposes as well,” Indyk says.
Squaring off
Edit distance is the minimum number of edits—deletions, insertions, and substitutions—required to turn one string into another. The standard algorithm for determining edit distance, known as the Wagner-Fischer algorithm, assigns each symbol of one string to a column in a giant grid and each symbol of the other string to a row. Then, starting in the upper left-hand corner and flooding diagonally across the grid, it fills in each square with the number of edits required to turn the string ending with the corresponding column into the string ending with the corresponding row.
Computer scientists measure algorithmic efficiency as computation time relative to the number of elements the algorithm manipulates. Since the Wagner-Fischer algorithm has to fill in every square of its grid, its running time is proportional to the product of the lengths of the two strings it’s considering. Double the lengths of the strings, and the running time quadruples. In computer parlance, the algorithm runs in quadratic time.
That may not sound terribly efficient, but quadratic time is much better than exponential time, which means that running time is proportional to N2, where N is the number of elements the algorithm manipulates. If on some machine a quadratic-time algorithm took, say, a hundredth of a second to process 100 elements, an exponential-time algorithm would take about 100 quintillion years.
Theoretical computer science is particularly concerned with a class of problems known as NP-complete. Most researchers believe that NP-complete problems take exponential time to solve, but no one’s been able to prove it. In their STOC paper, Indyk and his student Artūrs Bačkurs demonstrate that if it’s possible to solve the edit-distance problem in less-than-quadratic time, then it’s possible to solve an NP-complete problem in less-than-exponential time. Most researchers in the computational-complexity community will take that as strong evidence that no subquadratic solution to the edit-distance problem exists
Can’t get no satisfaction

The core NP-complete problem is known as the “satisfiability problem”: Given a host of logical constraints, is it possible to satisfy them all? For instance, say you’re throwing a dinner party, and you’re trying to decide whom to invite. You may face a number of constraints: Either Alice or Bob will have to stay home with the kids, so they can’t both come; if you invite Cindy and Dave, you’ll have to invite the rest of the book club, or they’ll know they were excluded; Ellen will bring either her husband, Fred, or her lover, George, but not both; and so on. Is there an invitation list that meets all those constraints?
In Indyk and Bačkurs’ proof, they propose that, faced with a satisfiability problem, you split the variables into two groups of roughly equivalent size: Alice, Bob, and Cindy go into one, but Walt, Yvonne, and Zack go into the other. Then, for each group, you solve for all the pertinent constraints. This could be a massively complex calculation, but not nearly as complex as solving for the group as a whole. If, for instance, Alice has a restraining order out on Zack, it doesn’t matter, because they fall in separate subgroups: It’s a constraint that doesn’t have to be met.
At this point, the problem of reconciling the solutions for the two subgroups—factoring in constraints like Alice’s restraining order—becomes a version of the edit-distance problem. And if it were possible to solve the edit-distance problem in subquadratic time, it would be possible to solve the satisfiability problem in subexponential time.
“This is really nice work,” says Barna Saha, an assistant professor of computer science at the University of Massachusetts atAmherst. “There are lots of people who have been working on this problem, because it has a big practical impact. But they won’t keep trying to develop a subquadratic algorithm, because that seems very unlikely to happen, given the result of this paper.”
As for the conjecture that the MIT researchers’ proof depends on—that NP-complete problems can’t be solved in subexponential time—”It’s a very widely believed conjecture,” Saha says. “And there are many other results in this low-polynomial-time complexity domain that rely on this conjecture.

References:http://phys.org/

From driving water wheels to turning turbines, water has been used as the prime mover of machinery and the powerhouse of industry for many centuries. In ancient times, the forces of flowing water were even harnessed to power the first rudimentary clocks. Now, engineers at Stanford University have created the world’s first water-operated computer. Using magnetized particles flowing through a micro-miniature network of channels, the machine runs like clockwork and is claimed to be capable of performing complex logical operations.

Using poppy-seed sized droplets of water impregnated with magnetic nanoparticles (those handy little elements being used in everything from drug delivery in humans to creating e-paper whiteboards), the new fluidic computer uses electromagnetic fields to accurately pump these droplets around a set of physical gates to perform logical operations. Suspended in oil and timed to move in very specific steps, the droplets in the system can theoretically be used to accomplish any process that a normal electronic computer can, albeit at considerably slower speeds.

Stanford assistant professor Manu Prakash has spent almost a decade thinking about such a device, ever since he was a graduate student. The many and varied components required of a fluidic computer have slowly coalesced in his mind over that time, with the most fundamental component of all – an accurate operating clock to drive the logic – being the crucial element in bringing his invention to fruition. Ultimately, Prakash built a rotating magnetic field to synchronize the flow of all the droplets in a precisely timed manner, and act as the clock.

“The reason computers work so precisely is that every operation happens synchronously; it’s what made digital logic so powerful in the first place,” says Prakash. “In this work, we finally demonstrate a synchronous, universal droplet logic and control.”

According to the Stanford researchers, this new type of computer offers up a way to produce an alternative to high-speed, complex, electronic computers and take logic processing to the physical world. In this way, the fluidic computer may find applications in such areas as biology, chemistry, and other physical sciences and technology that use processes more akin to the properties of organization found in nature.

“We already have digital computers to process information,” says Prakash. “Our goal is not to compete with electronic computers or to operate word processors on this. Our goal is to build a completely new class of computers that can precisely control and manipulate physical matter. Imagine if when you run a set of computations that not only information is processed but physical matter is algorithmically manipulated as well. We have just made this possible at the mesoscale.”

To create the fluidic logic, Prakash and Stanford graduate student Georgios Katsikis constructed assortments of miniscule iron blocks on glass slides to act as physical logic gates. Resembling a Pac-Man maze, the whole structure is filled with oil and topped with a clear glass slide, so that the fluid is sandwiched between the layers. To this, the researchers syringe in separate magnetic-nanoparticle-infused droplets of water.

They then surrounded the device with a series of large electromagnetic coils that, when turned on induce a magnetic field in the iron bars. As this magnetic field has its polarity alternately and continuously changed, so too there is a change in the induced magnetic field of the iron bars, and the magnetized water droplets are drawn around the circuit. Each alternation of the electromagnetic field amounts to one clock cycle, and each drop moves exactly one step onward with each of these cycles.

To observe the process, a video camera is used to capture the exchanges between individual droplets, and to observe fluidic computation in real time. As such, the ones and zeroes of binary code are represented by the presence or absence of a water droplet, with the magnetically-induced clock cycle ensuring that the droplets transfer in a flawless symphony that, the researchers believe, means the system can practically run forever without errors.

“Following these rules, we’ve demonstrated that we can make all the universal logic gates used in electronics, simply by changing the layout of the bars on the chip,” says Katsikis. “The actual design space in our platform is incredibly rich. Give us any Boolean logic circuit in the world, and we can build it with these little magnetic droplets moving around.”

The team also believes that, from the viewpoint of fundamental science, the work is exciting because it provides a new aspect on computation in the physical world. As such, just as the physics of calculation have been used to understand the limits of electronic computation, now the physical features of bits of information may be exploited in some novel way to control matter at the mesoscale (10 microns to 1 mm).

Given that the new system is also physically strong compared to electronic devices and adheres to universal design rules, Prakash and his team intend to produce a design tool for these fluidic circuits for anyone to use.

“We’re very interested in engaging anybody and everybody who wants to play, to enable everyone to design new circuits based on building blocks we describe in this paper or discover new blocks,” Prakash says. “Right now, anyone can put these circuits together to form a complex droplet processor with no external control – something that was a very difficult challenge previously. If you look back at big advances in society, computation takes a special place. We are trying to bring the same kind of exponential scale up because of computation we saw in the digital world into the physical world.”

References:http://www.gizmag.com/

HGST’s Ultrastar Archive Ha10 is aimed at enterprise users

We first caught wind of HGST’s high capacity hard drives in 2012, when the company claimed it could boost storage capacities by 40 percent by replacing regular old air inside the drive enclosure with helium. The Western Digital subsidiary stayed the course, producing a helium-based 6 TB HDD in 2013 and 8 TB model in 2014, and has now continued the upward trend with the world’s first 10 TB hard drive.

Aimed squarely at enterprise and data centers, the Ultrastar Archive Ha10 is the company’s latest take on a helium-based HDD. The apparent benefits of helium when it comes to HDD storage is its markedly lower density of around one-seventh that of regular air. This means less friction with internal moving parts, resulting in less power needed to drive the device and increased data density of the individual disks.

HGST calls its version of this HelioSeal and has combined it with shingled magnetic recording (SMR), a hard drive technology that records data on overlapping rather than parallel tracks, much like roof shingles (hence the name). The company says this results in an industry-leading storage density, low power consumption and ever-reliable storage solution. However, since SMR requires the writing of entire tracks, the drive is suited for active archive duties rather than frequent update workloads.

Further to its mammoth storage capacity, the 3.5-in drive is rated at two million hours mean time between failure (MTBF) and a 10-15 unrecoverable reduced bit error rate with 600k load-unload cycles. It comes in SATA 6 Gbps and SAS Gbps varieties and HGST claims a 20 percent improvement in Watts per TB over the preceding Ultrastar He8.

To begin with, the Ultrastar Archive Ha10 will be available to cloud and OEM storage clients with the software capabilities to harness the density of the device.

References:http://www.gizmag.com/