Month: July 2014

Building a Heap

Binary heaps are binary trees that are sorted in such a way that the parent leaf is either greater or lesser than both of its child nodes. When the root node is the greatest and each parent is greater than its children, then it’s a max heap. In the opposite scenario, we have a min heap. When presented with an array, we simply line up each element in the array from left to right, top to bottom in a binary tree format.

For example, the array [1, 3, 6, 5, 9, 8] would correspond to the following binary tree, sorted as a min heap:

When presented with the problem of turning an array into a max heap, my initial thought was “Why don’t you just sort the array from greatest to least? Surely that will satisfy the binary condition without any fancy schmancy algorithms or recursion.”

Turns out, it doesn’t.

In order to solve this problem, you need to individually check each node and guarantee it follows the heap rule (that is, whether it is greater or lesser than its children if it’s, respectively, max or min heap).

Confused out of my mind, I consulted MIT Open Courseware’s lecture on the subject, and, after that, I was even more confused. Just to get the slightest idea of what I was dealing with, I decided to get a solution down in Xcode, whether it was great or faulty, and scripted out something like this:

1. Check every node in the tree if it follows the rule. If it doesn’t, switch the node with its parent.

2. Check the tree if each node follows the rule. If not, go back to step 1. If yes, then you win!

From a computational standpoint, the errors are fairly obvious. You’d have to check each node individually over and over again until you found the mistake, and then, you’d have to check the entire tree over again.

What might make more sense would be to check each node if it follows the rule and, if it doesn’t, check the parents recursively until you climb to the top of the tree, checking for errors along the way. This will rearrange the nodes in such a way that it fixed more errors more efficiently. My original solution does not “bubble-up” through the entire tree.

I’ll have to fix this sometime in the future. In the meantime, I’m still working on breadth-first searches, Dijkstra’s theorem, and sorting by reversals. Hopefully those will be the subjects I touch upon in the future as I get my gears in shape.

My solution to Building a Heap can be found at https://github.com/HussainAther/rosalind/HEA.py

July 26, 2014

Science
Testing graphs for bipartiteness

Graphs are amazing.

Bipartiteness is a characteristic of certain graphs. A graph is bipartite if and only if you can color each node one of two two colors in such a way that no two adjacent nodes have the same color. Well, that’s the realization of the actual definition, which can be found here. The two-color definition is also the foundation for the algorithm I wrote that tests whether or not a graph is bipartite.

My solution can be found here:
https://github.com/HussainAther/rosalind/blob/master/BIP.py

July 24, 2014

Science
de Brujin graphs and Velvet Optimiser

I’m working with the Velvet Assembler as part of my virus identification project. When I’m not trying to write a perl module to complement the already-bulky script files that I’m working with, I like to do something that I usually wish most other bioinformatics scientists I’ve met would do as well: I like to delve into the mathematics behind the program.
Velvet Assembler constructs de Brujin graphs in a manner like so:

source

Confusing, right? Velvet uses the separated small reads to make overlapping regions that be analyzed for errors and compressed for simplicity. These small reads are constructed into a de Brujin graph, which contains a list of all the overlapping segments. See those arrows in the picture above? Those are edges. And the rectangles are our nodes. We have to tell the computer the rules of how to play the game of read alignment before it can go crazy in the sandbox, so we’ve decided on a directed graph that can follow certain parameters. When the ending of one region connects with another, it forms a “bubble” that can be corrected using the Tour Bus algorithm, which is similar to the Dijkstra’s algorithm, which we’ll get to in another post.

And that’s basically all I need to know about it for my research project. But, as with most mathematical oddities, that’s not as much as I want to know.

With the help of my friend, Rosalind, I was introduced to de Brujin graphs. To construct one, we could easily write a program that iterates through a list of k-mers from each given segment and, then, record the ones that overlap by all but one of their base pairs. (My solution for the Rosalind problem can be found here, by the way.) This raises a lot of questions about how to reconstruct an entire genome from the smaller segments. The favorite problem of every computer scientist, the Traveling Salesman Problem, (and in some cases, something a bit more unique) arises when we have to decide what is the best way to connect each smaller segment into a larger picture.

I hope to optimize the Velvet Assembler portion of the Virus Detection program with a greater understanding of the mathematics behind it. So far, it seems that all my work simply relies on my ability to use different commands and put them in script files. And, recently, I’ve been bogged down with error message after error message in the implementation of a self-written subroutine module. Sometimes you need to relax with some puzzles. Even if the pieces are all so big that they overlap with one another.

July 17, 2014

Science
Suboptimal Alignment Algorithm

import distance

b=“GACTCCTTTGTTTGCCTTAAATAGATACATATTTACTCTTGACTCTTTTGTTGGCCTTAAATAGATACATATTTGTGCGACTCCACGAGTGATTCGTA”

a=“ATGGACTCCTTTGTTTGCCTTAAATAGATACATATTCAACAAGTGTGCACTTAGCCTTGCCGACTCCTTTGTTTGCCTTAAATAGATACATATTTG”

c=0

da=“”

db=“”

for j in range(32,41):

for i in range(len(a)-j):

c1=0

for k in range(len(b)-j):

if distance.hamming(a[i:i+j], b[k:k+j])<=3:

c1+=1

if c1>c:

c=c1

print c

c=0

da=a

db=b

a=db

b=da

for j in range(32,41):

for i in range(len(a)-j):

c1=0

for k in range(len(b)-j):

if distance.hamming(a[i:i+j], b[k:k+j])<=3:

c1+=1

if c1>c:

c=c1

print c

This code takes two DNA strings that share some short inexact repeat of 32-40 bp that may appear with slight modifications (each repeat differ by ≤3 changes/indels).

As you can see, this code is far from perfect. For one, it involves hardcoding in the sequence (a bad habit of mine). For another thing, anyone human being with at least half a brain will notice that this is essentially the same few lines of code repeated. What could be uglier than seeing the same thing twice? We could easily clean this up:

def func(a, b):

for j in range(32,41):

for i in range(len(a)-j):

c1=0

for k in range(len(b)-j):

if distance.hamming(a[i:i+j], b[k:k+j])<=3:

c1+=1

if c1>c:

c=c1

return c

print func(a, b)

print func(b, a)

Ahh, much better. I wanted to post it as an example of the importance of using functions, even if a script will only be run once or, perhaps, never at all. Now, if only we could do something about that hardcoding habit of mine…

Many of my scripts can be found on my Github page.

July 12, 2014

Science
Perl

Ever since I got to Ithaca at the Boyce Thompson Institute, I’ve had to learn how to program in Perl, a less elegant version of my weapon of choice, Python.

An underscore? Next, you’ll be telling me to use goto and watch the world burn.

My computer-esque tasks have included debugging a script that is used in genome analysis and moving parameters from bwa-align to bowtie2. It’s very tedious and mind-numbing to sift through all the scripts that I’ve been provided. I simply cannot absorb all the information necessary. This past week was especially brutal, given that it was the first week of Ramadan and, therefore, I’ve been running on empty. No, literally, running on empty. But I don’t want to be a drama-queen about fasting. This happens every year. Though my productivity has dropped from ~40 hours/week to ~30 hours this past week, it’s worth mentioning that I have been able to concentrate on certain tasks more, even if it means working on them for a smaller number of hours.

Anyways, about the research, identifying the specific exonic regions of the tomato genome requires novel ways of sequencing, namely, using multi-exonic sites. (This article that I linked to is not part of our research, but, rather for reference about the exotic sites of RNA).

Where do the introns go in the winter?

But my work isn’t tedious because it’s on a computer, nor because I have to learn a lot of different protocols and techniques. My work is tedious because it involves a lot of careful, deliberate button-pressing in editing and running software until we can get our program to do what the thing to do what we wanted it to do in the first place. I crave something more analytical, more innovative, but it makes sense that you have to start somewhere with beta testing.

Some things on my bucket list for the summer:
-Begin studying mathematics to prepare for physics next year. (My math skills have deteriorated since I haven’t taken a math class since junior year of high school.)
-Begin studying for the MCAT.
-Grind my nose to the concrete in research.
-My conscience: “That’s it. no more commitments!” Me: “But…but, I want to write a novel!” My conscience: “No, you need to focus.”

Despite my lofty academic goals, I’ve already begun to struggle in my classes. This past semester, my GPA dropped to a 3.6, after a stellar 3.9 during my first semester. There were a few things going on this past semester that were out of my control and definitely caused unnecessarily stress and a few other things here and there that I really made decisions about, but, ultimately, I just want to focus on improving and getting better. For one thing, I had to miss a biology test when I was in the hospital due to breathing problems and chest pain. My professor wouldn’t let me retake it, despite the policy of his syllabus. I spoke to an ombudsman, and he told me that, though he believes I should be able to retake it, there was nothing I could do to fix it. It was adding insult to injury, and my biology grade dropped from an A/A- to a B+.

Goals for the fall semester:
-Begin the student organization (that I can’t talk more about right now)
-Begin the Medical Ethics Circle as part of MAPS
-Focus on a few classes, and get more work done
-“Re”,”search”, hippie, hippie to the hip hip hop you don’t stop!

Let the world know that Hussain Ather will rise to his true academic potential.

July 6, 2014

Science

Dear blog, my source of reflection,

One thing that has occurred to me is that, in order to keep moving ahead in life, you need to routinely ask yourself why you are doing the things you do. For example, I’ve loved science since I don’t even know when, but I never really ask myself why I want to grind my nose in research or go to med school (if I even still want to). Let’s face it. I wasn’t born with an undying love for what I do. If the high school freshman I once was had seen my bioinformatics research projects that I’m currently doing, I would have gone running for the hills in any direction other than science.

I’m majoring in physics while doing research in bioinformatics with a premed track, and I’m also taking courses in philosophy, computer science, and biology. Confused? Me too. The reason I need to reflect upon these academic focuses is that I need to remember my purposes to identify where and how to move on in the next part of life.

Have I lost my focus?

When I was a freshman in high school, I fell in love with physics and mathematics. In my physics and geometry classes, the idea of putting forth a mathematical proof to describe the universe through deductive reasoning blew my mind. I began to consider the possibility of being an engineer or scientist when I grew up. I started to fantasize about how I could solve all the world’s problems through mathematics. Come sophomore year, and chemistry was my new weapon of choice. I saw this hierarchy of fundamental knowledge starting with math, then physics, and, finally chemistry. (I currently don’t believe that the universe is entirely applied math and everything can be explained through physics, but that’s beside the point). At that time in high school, I appreciated all things scientific, except for one key area in science: biology.

I was always confused out of my mind why math, physics, and chemistry were integrated so well with one another while biology was sitting at its own table with its own fantasies about the universe. I scratched my head in my introductory biology class wondering “Why on earth are we explaining this complex mechanism of photosynthesis through these arbitrarily drawn squares and circles? Does it really take a genius to sit there and say that one molecule attacks the other simply because you said so? Why are we wasting time in memorization and drawing pictures rather than reasoning and evaluating? Why are we sitting here and categorizing all the things in the world rather than actually using the categories for scientific inquiry? Where is the calculus?” Anyhow, in hindsight, I was definitely being too harsh and idealistic, like I usually am. Biology courses are not taught this way because biology is exclusive to math and physics, but, rather, because they are taught from a different angle. Albeit, I never enjoyed learning biology this way, but, nowadays, I understand that not everything has to be taught from the same scope as physics and chemistry are.

After my senior year of high school, I did a summer research program at a small, local college. The research program let me choose what I wanted to do a project about. Being the young Einstein-wannabe, I wanted to study physics or mathematics. Unfortunately, the college was only strong in biological and chemical research. But, being desperate to start a research project in anything scientifically-related for the sake of science itself, I began a project in which I studied the numbers of shrimp consumed by Hydra vulgaris. The research professor showed me the world of biostatistics, in which we use math and numbers to study biology.

This blew my mind. (Math? Statistics? And numbers? In biology? Maybe I could appreciate biology after all.) Somewhere here or there, I heard about the field of biophysics. This sounded like an amazingly perfect field for me to study because I could finally understand the elusively cryptic field of biology in something that I enjoyed.

When it was time for college, I started on a premed route (for reasons I’ll explain in the next paragraph or two. I don’t know how I’m structuring this blog post yet). I chose to major in physics just because. I also started to lurk around the university departmental websites for opportunities to join research labs. I started looking through physics labs, but, seeing as how I only had experience in biological research and statistics, I ended up joining a bioinformatics lab. This was also another check off my list of “Things I want to learn” because I’ve always wanted to learn how computer programming. During my second semester of college, I started having another affair. One night, as I was trying to fall asleep on a cold, January night, I woke up around midnight with one thought running through my mind:

Philosophy.

It made perfect sense. My love for science was not fueled by anything else other than the love of coming to solutions from problems. I chose physics because it was the most fundamental of the sciences and, frankly, the only one that really stood back and questioned the way we reason and look at the world, rather than the fields of chemistry and biology which were “structured” in their own way. I whipped out my laptop and signed up for the introductory logic course for the second semester. When I told the philosophy undergraduate advisor that I wanted to double-major in physics and philosophy, he was very pleased and excited by the reasons that I gave him. I could tell that I was unique in the way I looked at the world.

Needless to say, that introductory logic course was like a wake-up call from a thousand-year sleep.

But, if you’re paying attention, you probably remember that I’m a physics major, right? And I’m doing research in bioinformatics? Well, truth be told, I am doing physics research, too, but it’s VERY VERY slow. In fact, I haven’t accomplished anything in my physics lab during my freshman year. My physics research professor has been way too unresponsive with me, but, hopefully I can contact him at the beginning of next semester again to start getting the ball rolling. In the meantime, I found a look at this website from the IU School of Informatics and Computer Science. It seemed to be everything I’ve ever wanted to study, all in one place. I’m in the process of contacting the research professors who work for it in order to find a research opportunity that can perhaps replace my slow-moving, not-quite-dead-yet physics lab that I’m working in. Working in two research labs simultaneously shouldn’t be too big of an issue. Especially since I’m a theoretician.

Real talk. I’m a premed out of family pressure. Throughout high school, I never really found a legitimate reason for becoming a doctor, and, whenever I’d protest to my parents that I didn’t want to be a premed, they would tell me it was the best path that one could take, therefore, I should take it. They told me that going to med school and becoming a doctor was one of the highest honors that one could achieve. While studying science might get you a job for a few years, everyone would respect you as a doctor for a lifetime. But, ever since I can remember, I’ve always been idealistic. Too idealistic. In fact, only about a week ago I realized how cynically ideological my motives were that they weren’t concrete enough for you to weigh a piece of paper on it. I wasn’t obsessed by “achieving a high status in society” or “making a lot of money.” I wanted to obsess over math and science to achieve a creative bliss that transcended anything that this world could offer me. But, and maybe my parents always knew best, it’s better to have a realistic, sustainable goal in mind for the rest of your life. I never put much thought into the actual career path of being a doctor, nor into the routines and activities that doctors normally do. Among the myriad of activities that doctors do on a day-to-day basis, the only things that truly interested me from the beginning were surgery and research. Today, as I write this, I’ve found other incredibly fascinating ways to study medicine, including through informatics/computer science, policymaking, and ethical discussion. Physics, computer science, biology, and now philosophy? How on earth does medicine fit into this?

Being a pre-med and going off to study medicine has always been a love-hate relationship for me. There were times during my first semester of college when I seriously considered abandoning the track of being a doctor altogether after I realized the frustratingly structured path which denied any liberal pursuit of education. “Psychology? Why would I have to take a course in psychology?” I remember one of my close friends told me “You know, you don’t HAVE to be premed. Doctors barely do anything involving physics and mathematics anyway.” That really struck a chord with me. I couldn’t simultaneously worship the liberal studies of philosophy and physics while staying on a more conservative approach to becoming a doctor. Was it possible for me to love learning for the sake of learning and still tell myself that I wanted to be a doctor? So…why do I want to go to med school? Am I just too scared to tell my parents I don’t want to be a doctor?

I’m still looking for a reason.

I’ve come to reconcile the two worlds of research and medicine by telling people I want to do an MD-PhD program, but, even then, I need to develop a burning passion for why I want to be a doctor. And not something vague, generic, or uncultivated like “I want to help people” or “I want to find a cure for cancer.” I also can’t read the lives of other people and try to follow their footsteps. There has to be something that I do that gives me an undying love for medicine and health care like no one else has. I mean, look at this guy! He studied physics, philosophy, and mathematics during his undergraduate years and then went on to make amazing contributions to history, medicine, and so many different social sciences! Or what about this fellow? A physicist-philosopher? My dream come true! He has also written about medicine and medical ethics. Splendid.

This quest is not futile. I’m sitting in my dorm room at Cornell University in the middle of my bioinformatics internship. I’m studying how the non-coding RNA regions of tomatoes do things. That’s related to health and well-being, right? It’s a good start. But I need something deeper. Something that incorporates all my interests. As far as ethics is concerned (as it relates to my love for philosophy), I am interested in medical ethics, bioethics, and scientific ethics. I can check that off the list now. Physics?…I’ll come back to that later. Hopefully. Someday. Computer science and biology? Well, those are because I became obsessed with bioinformatics.

Maybe that’s the only reason I need to justify what I study. Because I fell in love with them. Maybe I don’t need some ultimate goal of becoming the president of the country or finding the cure for cancer. I mean, I got accepted into an internship at Cornell. I think I’m doing things right, right? I just need to keep checking in on myself.

Here I go off into the world of academics, waltzing with the devilishly charming demon of scientific knowledge through physics, computer science, biology, and everything in between. Where will I end up? Let the coffee pour and spin the roulette wheel of fortune before the day’s over. We’ll see what I can learn tomorrow.

People ask me what I’m studying. Sometimes I say physics. Sometimes I say medicine. Sometimes I say computer science. And sometimes I say none of the above. Where am I going in my life? Looking back, everything has only been a serendipitous walk through a very, very confusing maze of passion after passion.

Heuristic

Month: July 2014

Building a Heap

Testing graphs for bipartiteness

de Brujin graphs and Velvet Optimiser

Suboptimal Alignment Algorithm

Perl

Any way the wind blows