In a 2006 article, Jeannette Wing, then a professor of computer science at Carnegie Mellon University, discussed computational thinking as “a way of solving problems, designing systems, and understanding human behavior that draws on concepts fundamental to computer science.”1 Since then, Wing has assumed the position of assistant director of the National Science Foundation Computer and Information Science and Engineering Directorate. From that podium, she has promoted the idea that as computation, communications, and information become increasingly prominent throughout daily life, computational thinking becomes more useful to the economic, intellectual, and social well-being of everyone (Box 2.1).
Wing’s presentation at the workshop made prominent mention of the “shotgun” approach to sequencing the human genome as a powerful example of how computational thinking might be useful outside the traditional domain of computer science. The human DNA sequence consists of 3.4 billion base pairs, and the determination of this sequence was completed in 2003, in a significantly shorter time than originally estimated, through the use of the shotgun approach. In general, the sequencing of a long DNA string can be accomplished only by dividing the sequence into a number of short fragments, each of which is sequenced and then assembled into the appropriate order.
In the shotgun approach, a long DNA sequence is randomly divided into many short fragments, each of which can be sequenced. To reassemble the fragments, investigators use overlaps between the ends of the fragments—fragments whose ends do not match cannot be connected to each other. However, the presence of a match between fragment ends does not guarantee that the two fragments in question should necessarily be joined, and additional data are needed to resolve these ambiguities. To obtain the additional data, the fragmentation process is repeated—since the division is random, it is likely that the spot where two fragments were separated in the first fragmentation will in fact be contiguous in the second fragmentation. This fact can be used to confirm or reject the match proposed from the first round. Through a series of successive rounds of fragmentation and analysis, the correct sequence can be determined. The algorithm used to analyze the data resulting from this iterative process is widely known as a shotgun algorithm.
This example manifests several aspects of computational thinking. Algorithm embodies the notion of a precisely formulated unambiguous