Computational Biology and Bioinformatics

Summary

In previous chapters you learned how to draw simple geometric shapes in a graphics window. Although you also learned how to manipulate these pictures somewhat using the mouse, they were otherwise static. In this chapter I will explain how to make these pictures dynamic; that is, how to program animations. In doing so you will learn several new ideas, such as how to use timers and how to use polymorphism and type classes in unique ways.

module Animation where

import Shape

import Draw

import Picture

import SOEGraphics hiding (Region)

import qualified SOEGraphics as G (Region)

import Win32Misc (timeGetTime)

import Word (word32ToInt)

What is an Animation?

An animation is a continuous, time-varying image. However, the animations that you see in the movies, on TV, or on your computer screen only seem to be moving continuously. In reality they are created by a sequence of static images - called frames that are displayed in such rapid succession that they appear to be continuous to the human eye. The rate at which this phenomenon occurs is somewhere between 20 and 30 times per second, depending on lighting conditions and other factors. I will use the rate of 30 times per second, or 30 Hertz, abbreviated 30 Hz. Televisions, computers, and motion pictures all use this fundamental physiological phenomenon to give the illusion of continuous movement.

So the question is, how do we program an animation? The only graphics 10 operation that we have discussed so far is drawInWindow, but note that drawing things using this operation is accumulative. That is, we never erase anything, nor even do so much as clear the screen. Even the user interaction given in Chapter 10 does not clear the screen; each successive rendition of the stack of regions is drawn right over the previous rendition. This works because each new picture completely hides the old one.

This will not work, however, if we are drawing a person walking across the screen, or a ball bouncing in a box.

Summary

All of the types considered thus far have been first order. For example, the type constructor Tree has always been paired with an argument, as in Tree Int (a tree containing Int values) or Tree a (representing the family of trees containing a values). But Tree by itself is a type constructor: something that takes a type as an argument and returns a type as a result. There are no values in Haskell that have this type, but such “higher-order” types can be used in class declarations in useful ways, as we shall see in this chapter.

The Functor Class

To begin, consider the following Functor class defined in the Standard Prelude:

class Functor f where

fmap :: (a → b) → f a → f b

DETAILS

Type applications are written in the same manner as function applications, and are also left associative: The type T a b is equivalent to ((T a) b).

There is something new here. The type variable f is applied to other types, as in f a and f b. Thus, we would expect f to be a type such as Tree, which can be applied to an argument. Indeed, a suitable instance of Functor for type Tree would be:

instance Functor Tree where

fmap f (Leaf x) = Leaf (f x)

fmap f (Branch t1 t2) = Branch (fmap f t1) (fmap f t2)

Recall that in Section 7.2 we defined a function mapTree that behaved just as the above fmap method, so we could have instead written:

“instanceFunctor Treewhere

fmap = mapTree

Such an instance declaration declares that Tree, rather than Tree a, is an instance of Functor.

Note that in Haskell we write Tree Int for trees of integers, and we say that Tree is a type constructor. And we write [Int] for lists of integers. However, what is the type constructor for lists? Because of Haskell's special syntax for the list data type, there is also a special syntax for its type constructor, namely [].

Summary

Recall that in Chapter 6 we used an infinite list to simulate a mathematical sequence used in the calculation or the perimeter of an ellipse. When a list is used in a context where it will always he infinite, it is commonly called a stream, Many problems can be elegantly, concisely, and efficiently expressed using streams, which we will explore in this chapter. With the power of streams there are also inherent dangers, which we will also explore. In the next chapter we will use streams in a central way in the implementation of a language for expressing reactive animations.

Lazy Evaluation

Because streams are never finite, it would seem natural to define a special polymorphic data type for them, such as:

data Stream a = a : Stream a

Although we could certainly do this, it is more convenient to use Haskell lists to “simulate” streams by just never using the empty list constructor []. The main advantage of this approach is that we can then reuse many polymorphic functions already defined on lists rather than redefining them on a new data type.

In Chapter 6 we used list comprehensions to create the infinite list [2, 2.], but is there a more fundamental way to create this list? Here is one way:

twos = 2 : twos

Let's compute this value by calculation:

twos

⇒ 2 : twos

⇒ 2 : 2 : twos

⇒ 2 : 2 : 2 : twos

…

There is, of course, no end to this calculation, An important distinction exists, however, between this calculation and ones that we have labeled as “infinite loops” and given the value ⊥ in previous chapters: this calculation is producing useful information, namely the successive elements of a list. Its value is an infinite list, or stream, A stream contains an infinite amount of information, whereas ⊥ contains no information whatsoever.

DETAILS

Try running this example, in Hugs, if you type twos to the evaluation prompt, it will go into an infinite loop printing 2's.

Now consider the expression head twos.

Summary

You have now seen several examples where functions are passed as arguments to other functions, such as with fold and map. In this chapter, I will show several examples where functions are also returned as values. This will lead to several techniques for improving definitions that we have already written - techniques that we will use often in the remainder of the text.

Currying

The first improvement relates to the notation we have used to write function applications, such as simple x y z. Although I have noted the similarity of this to the mathematical notation simple(x, y, z), in fact, there is an important difference, namely that simple x y z is actually equivalent to (((simple x) y) z). In other words, function application is left associative, taking one argument at a time.

Let's look at the expression (((simple x) y) z) a bit closer: There is an application of simple to x, the result of which is applied to y; so (simple x) must be a function! The result of this application, ((simple x) y), is then applied to z, so ((simple x) y) must also be a function!

Because each of these intermediate applications yields a function, it seems perfectly reasonable to define a function such as:

multSumByFive = simple 5

What is simple 5? From the above argument, we know that it must be a function. And from the definition of simple in Section 1.1, we might guess that this function takes two arguments, and returns 5 times their sum.

Indeed, we can calculate this result as follows:

multSumByFive a b

⇒ (simple 5) a b

⇒ simple 5 a b

⇒ 5 * (a + b)

Summary

The use of lists is particularly common when programming in Haskell, and thus, not surprisingly, there are many predefined polymorphic functions for lists. The list data type itself, plus some of the most useful functions on it, are contained in the Standard Prelude's PreludeList module, which I will cover in detail in this chapter. There is also a Standard Library module called List that has additional useful functions. It is a good idea to become familiar with both modules.

Although this chapter may feel like a long list of “Haskell features,” the functions described here capture many common patterns of list usage that have been discovered by functional programmers over many years of trials and tribulations. In many ways higher-order declarative programming with lists takes the place of lower-level imperative control structures in more conventional languages. By becoming familiar with these list functions you will be able to more quickly and confidently develop your own applications using lists. Furthermore, if all of us do this, we will have a common vocabulary with which to understand each others' programs. Finally, by reading through the code in this module you will develop a good feel for how to write proper function definitions in Haskell.

It is not necessary for you to understand the details of every function, but you should try to get a sense for what is available so that you can return later when your programming needs demand it. In the long run, you are well-advised to read the rest of the Standard Prelude as well as the various Standard Libraries, to discover a host of other functions and data types that you might someday find useful in your own work.

The PreludeList Module

To get a feel for the PreludeList module, let's first look at its module declaration:

module PreludeList (

map, (++), filter, concat,

head, last, tail, init, null, length, (!!),

foldl, foldl1, scanl, scanl1, foldr, foldr1, scanr, scanr1,

iterate, repeat, replicate, cycle,

take, drop, splitAt, takeWhile, dropWhile, span, break,

lines, words, unlines, unwords, reverse, and, or,

any, all, elem, notElem, lookup,

Summary

In Chapter 20 I defined a language called MDL for describing musical structures. The question now is, how do we actually interpret the structures; that is, how do we turn them into real music? (This is analogous to the question of how to draw a Shape or Region value in a graphics window.) The approach I will take will be to convert a Music value into a Standard MIDI File, which can then be played on your computer using any standard media player. I will do this, however, in three steps:

Summary

In the previous chapter you learned quite a few techniques for problem solving via calculation in Haskell It's time now to apply these ideas to a larger example, which will require learning even more problem-solving skills and Haskell language features.

Our job will be to design a simple module of geometric shapes, that is, a collection of functions and data types for computing with geometric shapes such as circles, squares, triangles, and others. Users of this module will be able to create new instances of geometric shapes and compute their areas. You will learn lots of new things in building this module, including how to design your own data types. Then in Chapter 4 we will extend this functionality with the ability to draw geometric shapes, and in Chapter 6 compute their perimeters.

In the description above I refer to the end product as a module, through which a user has access to certain well-defined functionalities. A module can be seen as a way to conveniently wrap up an application in such a way that only the functionality intended for the end-user is visible; everything else needed to implement the system is effectively hidden.

In Haskell we can create a module named Shape in the following way:

module Shape (…) where

…body-of-module…

The “(…)” after the name Shape will ultimately be a list of names of the functions and data types that the end-user is intended to use, and is sometimes called the interface to a module. At the end of this chapter we will fill in the details of the interface once we know what they should be. The …body-of-module… is of course where we will place all the code developed in this chapter.

DETAILS

Module names must always be capitalized (just like type names).

A user of our shape module can later import it into a module that he or she is constructing, by writing:

import Shape

Indeed, we will do exactly this in later chapters where new modules will be created in which users will be able to draw shapes, compute their perimeters, combine them into larger “regions,” color them, scale them, and place them on a “virtual desktop.”

Summary

In Chapters 2 and 8 we defined modules for geometric shapes and regions, respectively. We will now build a third layer onto this structure: a module that provides the ability to color regions and to place them on a “virtual desktop” in a graphics window. These colored regions will be called pictures. Once placed, you will be able to “click” on a picture using the mouse, which will cause that picture to rise to the surface of the desktop (i.e., any objects partially occluding it will be pushed beneath it). As usual, I will begin the discussion by providing the module interface:

module Picture (Picture (Region, Over, EmptyPic),

Color (Black, Blue, Green, Cyan, Red, Magenta, Yellow, White),

regionToGRegion, shapeToGRegion,

drawRegionlnWindow, drawPic, draw, spaceClose,

module Region

) where

import Draw

import Region

import SOEGraphics hiding (Region)

import qualified SOEGraphics as G (Region)

DETAILS

The last two lines above look strange, and arise because both the Region module and the SOEGraphics module define a data type called Region, so importing them both into the same module causes a name clash, which Haskell (quite sensibly) does not. allow. In order to use them both, I first import afl of the SOEGraphics module except for Region; that's what the next to the last line does. Then I import SOEGraphks as a qualified module, at the same time renaming if to G, and furthermore I only import Region from it, All of this is achieved by the last line above, The end result is that in the Picture module, the Region data type defined in SOEGraphics has the name G.Region, whereas the one from module Region is just called Region. (If I had omitted “as G” from the last line above, then the new Region type would be referred to as SOEGraphics. Region.)

Note that the Region module is imported and exported; and recall that the Region module includes the Shape module.

Summary

In this section Haskell's pattern-matching process will be explained in greater detail. Haskell defines a fixed set of patterns for use in case expressions and function definitions. Pattern matching is permitted using the constructors of any type, whether user-defined or predefined in Haskell. This includes tuples, strings, numbers, characters, and so on. For example, here's a contrived function that matches against a tuple of “constants:”

contrived :: ([a], Char, (Int, Float), String, Bool) → Bool

contrived ([], ′b′ (1, 2.0), “hi”, True)

= False

This example also demonstrates that nesting of patterns is permitted (to arbitrary depth).

Technically speaking, formal parameters to functions are also patterns – it's just that they never fail to match a value. As a “side effect” of a successful match, the formal parameter is bound to the value it is being matched against. For this reason, patterns in any one equation are not allowed to have more than dne occurrence of the same formal parameter.

A pattern that may fail to match is said to be refutable; for example, the empty list [ ] is refutable. Patterns such as formal parameters that never fail to match are said to be irrefutable. There are two other kinds of irrefutable patterns, which are summarized below.

The first pattern is known as a wildcard. Another common situation is matching against a value we really care nothing about. For example, the functions head and tail can be written as:

head (x :-) = x

tail (-: xs) = xs

in which we have “advertised” the fact that we don't care what a certain part of the input is. Each wildcard will independently match anything, but in contrast to a formal parameter, each will bind nothing; for this reason more than one are allowed in an equation.

The second kind of irrefutable pattern in Haskell is called a lazy pattern, and has the form ̃pat.

Summary

Programming, in its broadest sense, is problem solving. It begins when we look out into the world and see problems that we want to solve, problems that we think can and should be solved using a digital computer. Understanding the problem well is the first – and probably the most important step in programming, because without that understanding we may find ourselves wandering aimlessly down a dead-end alley, or worse, down a fruitless alley with no end. “Solving the wrong problem” is a phrase often heard in many contexts, and we certainly don't want to be victims of that crime. So the first step in programming is answering the question, “What problem am I trying to solve?”

Once you understand the problem, then you must find a solution. This may not be easy, of course, and in fact you may discover several solutions, so we also need a way to measure success. There are various dimensions in which to do this, including correctness (“Will I get the right answer?”) and efficiency (“Will I have enough resources?”). But the distinction of which solution is better is not always clear, because the number of dimensions can be large, and programs will often excel in one dimension and do poorly in others. For example, there may be one solution that is fastest, one that uses the least amount of memory, and one that is easiest to understand. Choosing can be difficult and is one of the more interesting challenges that you will face in programming.

The last measure of success mentioned above – clarity of a program – is somewhat elusive, most difficult to measure, and, quite frankly, sometimes difficult to rationalize. But in large software systems clarity is an especially important goal, because the most important maxim about such systems is that they are never really finished! The process of continuing work on a software system after it is delivered to users is what software engineers call software maintenance, and is the most expensive phase of the so-called “software lifecycle.”

Summary

It is possible to use a language such as FAL to control thongs other than graphics images and animations. In particular, one could use FAL to control robots, not only in terms of their dynamic movement, but also their interaction with the real world. This is an interesting declarative approach to robot control that some researchers have in fact pursued. However, I will not do so here, for two reasons: First, there are no inexpensive, standard robots that I could use to make this effort truly worthwhile (although this may change over the next few years). Second, to demonstrate this idea using a graphically simulated robot would not make it significantly different from what I have already done with FAL.

Therefore, in this chapter I will describe a simple imperative language for robot control, using a simple graphics image to simulate the robot motion. My purpose is primarily to demonstrate the use of monads to implement stateful (i.e., imperative) computations. The language, which I will call IRL (for “imperative robot language”), is much less sophisticated than FAL, although it still qualifies as an embedded DSL.

The implementation also uses a new data structure, an array, as part of the representation of the state of the robot's world. An array is functionally no different from an indexed list, but is more efficient in access time.

module Robot where

import Array

import List

import Monad

import SOEGraphics

Import Win32Misc (timeGetTime)

import qualified GraphicsWindows as GW (getEvent)

IEL by Example

As I did with FAL, I will begin with a brief description of how to program in IRLS and return to its implementation in the next section. Being an imperative language, the essence of IRL is a set of commands. These operations must be sequenced properly to achieve some desired behavior. Not surprisingly, it is most convenient to use the do syntax to achieve this, implying that the underlying structure is a monad.

Summary

Recall that a polymorphic type such as (a → a) is really shorthand for ∀(a)a → a, which can be read “for all types a, functions mapping elements of type a to elements of type a.” Note the emphasis on for all.

In practice, however, there are times when we would prefer to limit a polymorphic type to a smaller number of possibilities. A good example is a function such as (+). It's probably not a good idea to limit (+) to a single (that is, monomorphic) type such as Integer → Integer → Integer, because there are other kinds of numbers - such as floating-point and complex numbers - that we would like to perform addition on. Nor is it a very good idea to have a different addition function for each type of number we wish to add, because that would require giving each a different name, such as addlnteger, addFloat, addComplex, and so on. And, unfortunately, we can't give (+) a type such as a → a → a, because this would imply that we could add things other than numbers, such as characters, lists, tuples, and any type that you might define on your own!

Haskell provides a solution to this problem through the use of qualified types. Conceptually, you can think of a qualified type just as a polymorphic type, except that in place of “for all types a” we will be able to say “for all types a that are members of class C”, where the class C can be thought of as a set of types. For example, suppose there is a class Num with members Integer, Float, and Complex. Then we could give an accurate type for (+), namely: ∀(a ε Num)a → a → a. But in Haskell, instead of writing ∀(a ε Num) … we will write Num a ⇒ ….

Summary

In this chapter simple graphics programming in Haskell will be explained. Graphics in Haskell is consistent with the notion of computation via calculation, although it is special enough to warrant the use of special terminology and notation. In the next chapter we will use the techniques learned here to draw in a graphics window the geometric shapes defined in the last chapter. The ideas developed in this chapter will be put into a module called SimpleGraphics:

module SimpleGraphics where

There are many predefined functions and data types in Haskell, so many, in fact, that they demand some organization. Entities that are deemed essential to defining the fundamental nature of Haskell are contained in what is called the Standard Prelude, a collection of modules defining various categories of functionality. Entities that are deemed useful but not essential are contained in one of several Standard Libraries, also a collection of modules. The entire Standard Prelude is automatically imported into every program that you write, whereas the Standard Libraries need to be imported module-by-module.

Unfortunately, there is no standard graphics library for Haskell yet, although there is one in popular use on Windows machines called Graphics. The basic graphics functionality that we will use is defined in a library called SOEGraphics, which is very similar to Graphics but is guaranteed to work with this textbook, whereas the Graphics library may evolve over time. To use SOEGraphics, it must be imported into the module that is using it, as follows:

import SOEGraphics

Graphics is a special case of input/output (IO) processing in Haskell, and thus I will begin with a discussion of this more general idea.

Basic Input/Output

The Haskell Report defines the result of a program as the value of the name main in the module Main. On the other hand, the Hugs implementation of Haskell allows you to type whatever expression you wish to the Hugs prompt, and it will evaluate it for you.

Summary

Many interesting RNAs conserve a secondary structure of base-pairing interactions more than they conserve their sequence. This makes RNA sequence analysis more complicated and difficult than protein or DNA sequence analysis. RNA secondary structure problems are a natural application for probabilistic models based on the stochastic context-free grammars introduced in Chapter 9. In this chapter, we will examine two RNA analysis problems of biological interest.

The first problem is RNA secondary structure prediction for a single sequence. We will outline two well-known dynamic programming algorithms for RNA secondary structure prediction, the Nussinov and the Zuker algorithms. Then we will use RNA secondary structure prediction as an introductory example for the use of SCFGs for RNA analysis, by developing a small SCFG that implements a probabilistic version of the Nussinov algorithm.

The second is a related set of problems, having to do with the analysis of multiple alignments of families of related RNAs. Like Chapter 5, where profile HMMs were used for both multiple alignment and for database searching, we develop RNA structure profiles called ‘covariance models’ (CMs) for dealing with RNA multiple alignments with secondary structure constraints included. Covariance models are used for both RNA multiple alignment and database searches. Consensus structure prediction from RNA multiple alignments, a process called comparative RNA sequence analysis, is also somewhat automated by RNA covariance model training algorithms.

As you read this chapter, bear in mind that SCFG-based RNA analysis methods are not widely known or used.

Summary

So far we have concentrated on the intrinsic properties of single sequences, such as CpG islands in DNA, or on pairwise alignment of sequences. However, functional biological sequences typically come in families, and many of the most powerful sequence analysis methods are based on identifying the relationship of an individual sequence to a sequence family. Sequences in a family will have diverged from each other in their primary sequence during evolution, having separated either by a duplication in the genome, or by speciation giving rise to corresponding sequences in related organisms. In either case they normally maintain the same or a related function. Therefore, identifying that a sequence belongs to a family, and aligning it to the other members, often allows inferences about its function.

If you already have a set of sequences belonging to a family, you can perform a database search for more members using pairwise alignment with one of the known family members as the query sequence. To be more thorough, you could even search with all the known members one by one. However, pairwise searching with any one of the members may not find sequences distantly related to the ones you have already. An alternative approach is to use statistical features of the whole set of sequences in the search. Similarly, even when family membership is clear, accurate alignment can be often be improved significantly by concentrating on features that are conserved in the whole family.

Summary

Until now, we have treated biological sequences as one-dimensional strings of independent, uncorrelated symbols. This assumption is computationally convenient but not structurally realistic. The three-dimensional folding of proteins and nucleic acids involves extensive physical interactions between residues that are not adjacent in primary sequence. Can probabilistic models of proteins and nucleic acid sequences be developed that allow for longer range interactions? Can we compute efficiently with such models? In this chapter, we will step back from models of particular sequence problems and address these more theoretical issues. We will see how many of the methods described in previous chapters fit into a more general view of modelling sequences

A general theory for modelling strings of symbols has been developed by computational linguists [Chomsky 1956; 1959]. This theory is known as the Chomsky hierarchy of transformational grammars. In the Chomsky hierarchy, most of the models we have used so far in this book are the lowest of four types of model of increasing complexity and descriptive power. Transformational grammars were developed in an attempt to understand the structure of natural languages. They became important in theoretical computer science [Hopcroft & Ullman 1979; Gersting 1993] because computer languages, unlike natural languages, can be precisely specified as formal grammars. Recently, transformational grammars have been applied to sequence analysis problems in molecular biology [Searls 1992; Dong & Searls 1994; Rosenblueth et al. 1996].

Computational Biology and Bioinformatics

Refine search

Refine search

Actions for selected content:

Save Search

1070 results in Computational Biology and Bioinformatics

Summary

Summary

Summary

Summary

Summary

Summary

Summary

Summary

Summary

Summary

Summary

Summary

Summary

Summary

Summary

Summary