Catalyzing Inquiry at the Interface of Computing and Biology

CULTURE AND RESEARCH INFRASTRUCTURE 339

bases. From the perspective of this report, Box 10.3 describes some of the essential intellectual aspects of
computer science that biologists must understand.
Recognizing that students might require competence at multiple levels depending on their needs,
the BIO2010 report identified three levels of competence as described in Box 10.4.

10.3 Barriers,

Essential Concepts of Computer Science for the Biologist

Key for the computer scientist is the notion of a field that focuses on information, on understanding of

computing activities through mathematical and engineering models and based on theory and abstraction, on

the ways of representing and processing information, and on the application of scientific principles and

methodologies to the development and maintenance of computer systems—whether they are composed of

hardware, software, or both.

There are many views of understanding the essential concepts of computer science. One view, developed in

1991 in the NRC report Computing the Future, is that the key intellectual themes in computing are algorithmic

thinking, the representation of information, and computer programs.^1

• An algorithm is an unambiguous sequence of steps for processing information. Of particular relevance is
  how the speed of the algorithm varies as a function of problem size—the topic of algorithmic complexity.
  Typically, a result from algorithmic complexity will indicate the scaling relationships between how long it
  takes to solve a problem and the size of the problem when the solution of the problem is based on a specific
  algorithm. Thus, algorithm A might solve a problem in a time of order N^2 , which means that a problem that is
  100 times as large would take 100^2 = 10,000 times as long to solve, whereas a faster algorithm B might solve
  the same problem in time of order N ln N, which means a problem 100 times as large would take 100 ln 100
  = 460.5 times as long to solve. Such results are important because all computer programs embed algorithms
  within them. Depending on the functional relationship between run time and problem size, a given program
  that works well on a small set of test data may—or may not—work well (run in a reasonable time) for a larger
  set of real data. Theoretical computer science thus imposes constraints on real programs that software devel-
  opers ignore at their own peril.


• The representation of information or a problem in an appropriate manner is often the first step in designing an
  algorithm, and the choice of one representation or another can make a problem easy or difficult, and its solution
  slow or fast. Two issues arise: (1) how should the abstraction be represented, and (2) how should the represen-
  tation be structured properly to allow efficient access for common operations? For example, a circle of radius 2
  can be represented by an equation of the form x^2 + y^2 = 4 or as a set of points on the circle ((0.00, 2.00), (0.25,
  1.98), (0.50, 1.94), (0.75, 1.85), (1.00, 1.73), (1.25, 1.56), (1.50, 1.32), (1.75, 0.97), (2.00, 0.00)), and so on.
  Depending on the purpose, one or the other of these representations may be more useful. If the circle of radius
  2 is just a special case of a problem in which circles of many different radii are involved, representation as an
  equation may be more appropriate. If many circles of radius 2 have to be drawn on a screen and speed is
  important, a listing of the points on the circle may provide a faster basis for drawing such circles.
  •A computer program expresses algorithms and structure information using a “programming language.”
  Such languages provide a way to represent an algorithm precisely enough that a “high-level” description (i.e.,
  one that is easily understood by humans) can be translated mechanically (“compiled”) into a “low-level”
  version that the computer can carry out (“execute”); the execution of a program by a computer is what allows
  the algorithm to be realized tangibly, instructing the computer to perform the tasks the person has requested.
  Computer programs are thus the essential link between intellectual constructs such as algorithms and informa-
  tion representations and the computers that perform useful tasks.

continued

(^1) The discussion below is adapted from Computer Science and Telecommunications Board, National Research Council, Computing the
Future: A Broader Agenda for Computer Science and Engineering, National Academy Press, Washington, DC, 1992.