Computer Science Project: Helping Solve a Problem in Bioinformatics

 

If you have ever been prescribed a drug, or seen an advertisement for one, you have probably noticed the list of potential side effects ranging from dizziness to death. A drug might cure one person, and poison another. I wondered why people respond differently to the same drugs, and decided to pursue a project in bioinformatics -- the science of analyzing genetic data --  to explore this question. I found that genetic mutations affect a person’s response, and coded an algorithm to locate these mutations in a genome. Research in this area could lead to groundbreaking medical innovations that would alleviate suffering by enabling personalized medicine, allowing doctors to create tailor-made treatments based on an individual’s unique genetic composition.

People responding differently to the same drug is a problem of increasing concern. For example, a CDC study found that 120,000 people are hospitalized per year for severe drug reactions. With over 70% of Americans on at least one prescription drug, the possibility of experiencing severe side effects is an imminent and potentially fatal risk. According to a study from the Journals of the American Medical Association, prescription drugs are the fourth leading cause of death in the USA, causing 106,000 deaths per year. This means that severe responses to drugs are a critical health concern.

Could there be a way to predict what drugs an individual will respond to? To help address this problem, I researched what could cause variable responses to some of the most common drugs Lipitor, Plavix, and Tegretol, and found that genetic mutations influence a person’s response. 

However, knowing the mutations only solves half the problem. Doctors need to know if their patients have particular mutations. They need to locate a single base swap in a genome of millions of bases by using a string searching algorithm. String searching algorithms are computer programs that locate a string of characters within a text. In this case, the genome is the text and the mutation, a sequence of base letters, is the string. It is important for the algorithm to produce a result quickly so that doctors can test a large volume of patients conveniently and easily. In addition, a fast algorithm is vital in emergency situations such as seizure or allergic shock when the correct drug must be prescribed immediately.

To help determine an optimal algorithm, I selected two of the most widely used string searching algorithms: Naive Exact Matching and Boyer-Moore, as well as the Boyer-Moore modification Apostolico-Giancarlo, and compared their efficiencies.

Efficiencies are determined by the number of character comparisons and string alignments each algorithm performs. The fewer comparisons and alignments it performs, the faster an algorithm runs. Character comparisons compare a letter in pattern P to a letter in text T, while the alignments compare the whole P to a small segment of T.  Since Boyer-Moore uses an efficient algorithm to skip certain alignments, it takes less time to run than Naive Exact Matching. Apostolico-Giancarlo is more efficient than Boyer-Moore because it stores each compared character in an array. For this reason, I parallelized it, or coded it to run simultaneously on multiple processors, to make it even faster.

    How does parallelism make an algorithm faster?

A parallel program divides the task of searching through a genome by making multiple processors work together on a problem. This reduces the time needed to obtain the solution.

    Structure of a parallel program

My results lead me to conclude that a parallelized algorithm is essential to feasible personalized medicine. Further research is needed, as this study only addresses several mutations specific to several drugs, and the Apostolico-Giancarlo algorithm is only one out of hundreds of possibly more efficient algorithms. However, these results suggest that bioinformatics research has the potential to save lives by allowing doctors to make the pill fit the ill.

I also made a video describing my project, which you can find here: https://www.youtube.com/watch?v=Vw3QYrqA99U