Skip to main content Accessibility help
Internet Explorer 11 is being discontinued by Microsoft in August 2021. If you have difficulties viewing the site on Internet Explorer 11 we recommend using a different browser such as Microsoft Edge, Google Chrome, Apple Safari or Mozilla Firefox.

Chapter 7: Dictionaries, Memoization, and Speed

Chapter 7: Dictionaries, Memoization, and Speed

pp. 100-115

Authors

, Harvey Mudd College, California, , Harvey Mudd College, California
Resources available Unlock the full potential of this textbook with additional resources. There are Instructor restricted resources available for this textbook. Explore resources
  • Add bookmark
  • Cite
  • Share

Summary

In the previous chapter we saw how to solve some important computational problems with the use-it-or-lose-it principle. This approach obtains the correct answer by effectively exploring every possible solution to a problem. Unfortunately, it turns out that this approach can get very slow as data sets get large. For example, on a typical personal computer, running the LCS function on two random strings, each of length 10, takes approximately one thousandth of a second. But on two strings of length 25 it takes a good part of an hour and on strings of length 100 (which is still very short by the standards of biologists working with real sequences) it would take, conservatively, well over a trillion years.

We began this part of the book with the problem of determining homology between the mammalian X and the bird Z chromosomes. To solve this problem, we’ll need to do over 1000 comparisons between proteins that are each hundreds of amino acids long. That will (almost literally) take forever!

About the book

Access options

Review the options below to login to check your access.

Purchase options

eTextbook
US$63.00
Hardback
US$110.00
Paperback
US$63.00

Have an access code?

To redeem an access code, please log in with your personal login.

If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.

Also available to purchase from these educational ebook suppliers