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!
Review the options below to login to check your access.
Log in with your Cambridge Aspire website account to check access.
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.