Sequence comparison


OK, so I got word through from the guy in charge of the computer course about my little ethical crisis. He suggested that, instead of posting actual code, I instead merely include pseudocode for the bits covered by the course. Now why the heck didn't I think of that?

On with the show. A major part of bioinformatics involves the comparison of different genetic sequences. Say you have a working gene for vitamin C production, plus something that you think might be a broken copy of same. How do you figure out whether they are actually related?

The basic technique is to figure out how many mutations (insertions, deletions, substitutions) it takes to get from one to the other. There are many many variants on this basic principle - tailor-made modifications designed to account for a variety of changeable factors such as:

1) are certain substitutions more common than others?
2) how likely are insertions and deletions of various sizes? (coughZipf distributioncough)
3) do certain subsections match better than others?

For this post, I'll only cover the most simple case: all three types of mutation are equally likely, and indels (insertions and deletions) are always of length 1.

Cutting it down to size

OK, so we have a couple of strings (referred to as S and T) to align - we'll think of this as finding a way to mutate S so it ends up looking like T. There's no immediately-obvious way of solving this, so let's try a standard approach: see if we can reduce it to a simpler problem.

I'm going to look at a few cases and show how they reduce to various easier problems, with examples of situations where each reductive approach can be ideal. Hope people can follow! I will be using the Python slice notation extensively, so you may want to familiarise yourself with that first.


OK, so say our two strings are "CAAATAGCAA" and "CCGCGAGCAA". There's something you should notice here: we don't actually need to do anything with the last 5 digits! We can just say "hey, they match", and stop worrying about them. The problem then reduces itself to trying to align "CAAAT" with "CCGCG". Much simpler.

Formally: if S[-1] and T[-1] are identical, they may be replaced by S[:-1] and T[:-1] at no cost.


Let's try a different set of strings. Say we have "AAATCCAGCA" and "AAATCCAGCT". Now, if you look at these, you'll see they differ by only the last element. Time for a substitution! If we transform the first string by substituting a T for the A, we'll then just be able to match the rest. Home and dry! This does "cost" us one mutation, but in this case that's a small price to pay.

Formally: S and T may be replaced by S[:-1] and T[:-1] at a cost of 1 mutation


Our next two example strings are "GGGTCATCTTA" and "GGGTCATCTT". Now, it should be fairly obvious what you need to do to the first string to get it to match the second: just delete the "A".

Formally: S may be replaced with S[:-1] at a cost of 1 mutation


Finally, consider the strings "CCGGAGACCT" and "CCGGAGACCTG". Our instinctive response here is to stick a G on the end of the first string. However, that presents us with a problem: if we're going to start adding stuff to strings, we're going to end up with longer strings. That ruins the whole idea of trying to simplify the problem.

There's a simple workaround - we just need to combine two operations. If we add a "G" and then immediately match the two "G"s away, we end up with the same result as if we'd simply dropped the "G" off the end of the second string. That's a lot more tractable, and incidentally is pleasingly symmetrical with the aforementioned operation of deletion.

Formally: T may be replaced by T[:-1] at a cost of 1 mutation

These are the only options for this model!

Shake it all about

OK, so let's combine these four approaches into a single algorithm. What we're going to do is take our pair of strings and apply each of the four abovementioned alterations to them (using matching or substitution as applicable). This will provide us with three pairs of strings, at least one of which will be shorter, which we can then apply the same method to. Eventually both strings will sink to size zero in every single case. We'll then select the sequence of operations that gets us to this point via the fewest expensive mutations.

We can write this more formally. Refer to the "distance" (number of mutations) between S and T as D(S,T). Then we have the following:

D(S,T) = min{
D(S[:-1],T[:-1]) + s(S[-1],T[-1])
D(S[:-1],T) + 1
D(S,T[:-1]) + 1

where s(A,B) = 1 if A and B are different letters and 0 if A and B are the same (this represents the cost of either substituting B for A or matching them)

If we implement this as a function that takes two strings and returns the distance between them, we can simply design it so that it recurses through all possible substrings. Puzzle solved!

A problem

We have, however, missed something. What happens if, say, we're comparing "ATGGCTA" with ""? The string T[:-1] will now no longer exist, and the program will crash horribly when it tries to evaluate D(S,T[:-1]). Doh.

Fortunately, there's an easy solution. Since the only way of getting from "ATGGCTA" to "" is by deleting all the letters, we can just say that this has a cost of 7 mutations. A similar approach applies if the first string is empty. We'll need to write this into the code:

if S=="": D(S,T) = len(T)

elif T=="": D(S,T) = len(S)

D(S,T) = min{
D(S[:-1],T[:-1]) + s(S[-1],T[-1])
D(S[:-1],T) + 1
D(S,T[:-1]) + 1

A computational note

If you decide to implement this alignment algorithm for yourself - and I strongly recommend you try it - you'll quickly notice a major problem with the standard recursive implementation of the algorithm. In short, it's damn slow for long strings. More precisely, since each distance calculation spawns three other distance calculations, the time required to run the thing will be somewhere on the order of 3 to the power of the length of the strings[1]. This sucks.

Fortunately, there's a much nicer approach, albeit one that requires a modicum more memory (try saying that three time fast...). The problem with the recursion is that it's wasting time by repeatedly calculating the same distance. Why not simply precalculate these values, and refer to them as necessary? One way of implementing this is by creating a grid such that element (i,j) of the grid is equal to D(S[:i],T[:j]). This can be populated by filling in the sides adjacent to D("","") and then working outwards from that corner.

A rather fuzzy mathematical note

It turns out, if I understand the book I'm currently reading correctly, that the problem solved here is part of a wider class of mathematical problems, which also includes things like determining RNA secondary structure. In particular, they're ones that in some rather abstract sense involve the concept of context-free grammars, and it turns out that you can solve them all in a similar fashion.

At present, I have sod-all idea how this works. However, as an incurable maths student, I'm very interested in exploring the theoretical underpinnings involved, and will probably rant on about this in some detail at a later date. Consider yourselves warned :)

The next step

In this post I've provided a fairly solid discussion of the basic alignment algorithm. The next post on this topic will be fairly brief, and will cover a phenomenon known as BLOSUM matrices that are used to fine-tune the alignment of two protein (not DNA) sequences.

[1] At some point it will actually be beneficial to have a detailed discussion of calculations of this sort. They come up in the real world a heck of a lot - for example, in cryptography, mathematicians can spend years of their lives trying to reduce an algorithm's runtime by a comparatively tiny-looking amount. The reason they do this is because that "tiny amount" can often be disproportionately important as the codes get harder to crack.


Anonymous Anonymous said...

sheena hentai sheena hentai sheena hentai sheena hentai

This a good link's !
Posted by Admin

1/26/2007 4:11 am  
Anonymous Anonymous said...

Auto News Press Digest

1/29/2007 5:41 am  
Anonymous Anonymous said...

hentai artist prophet hentai artist prophet hentai artist prophet hentai artist prophet

This a good link's !
Posted by Admin

1/29/2007 5:27 pm  
Anonymous Anonymous said...

hentai bdsm
hentai mature bdsm
hentai bdsm nyc
hentai bdsm master
hentai lesbian bdsm video
hentai bdsm pillory
hentai bdsm domination
hentai pandora peaks bdsm
hentai bdsm toy box

hentai young bbs
hentai vagina tgp
hentai naturist bbs
porno hentai
bbs hentai
pre teen hentais
free bbs hentais
incest art
teen incest
3d incest art
incest mom and son

1/30/2007 10:46 am  
Anonymous Anonymous said...

Auto show
Detroit Auto_Show
Car Insurance Agent
Car Insuranc _Agent
Great Drives
In Gear
Car New Models
Video Galleries

2/02/2007 5:33 pm  
Anonymous Anonymous said...

lolita chin
lolitas 13
lolitas kid
free anal sex
lolita picture
lolita suck
lolita cp terra loltobbs ftp lol
lolita vip lolitas virgins bbs
lolita lolly fuck movie children
lolita chin
lolitas 13
lolitas kid
free anal sex
lolita picture
lolita suck
lolita cp terra loltobbs ftp lol
lolita vip lolitas virgins bbs
lolita lolly fuck movie children

2/12/2007 8:41 pm  
Anonymous Anonymous said...

lolita chin
lolitas 13
lolitas kid
free anal sex
lolita picture
lolita suck
lolita cp terra loltobbs ftp lol
lolita vip lolitas virgins bbs
lolita lolly fuck movie children
lolita chin
lolitas 13
lolitas kid
free anal sex
lolita picture
lolita suck
lolita cp terra loltobbs ftp lol
lolita vip lolitas virgins bbs
lolita lolly fuck movie children

2/13/2007 5:50 am  
Anonymous Anonymous said...

Young Lolita
Nude stories

2/14/2007 12:27 pm  
Anonymous Anonymous said...

free bbs
little angels
porn gallery

2/16/2007 6:11 pm  
Anonymous Anonymous said...

free movie sex
hard sex video
young breasts Asian
porn lolita bbs
sex nymphet
image madonna sex hent
bbs lolita
asian bbs preteen
hentai free xxx password
hentai hole shemale
hentai wallpaper xxx
bbs child models
bbs child
bbs lolita smuggler
bbs posting prelolitas
iboard lolita bbs
nymphet links
pedo incest
sex pictures
britney spears sucks dick
Asian School Girls
asian bestiality

2/19/2007 9:14 pm  
Anonymous Anonymous said...

cheapest cruise vacation packages

2/24/2007 3:20 pm  
Anonymous Anonymous said...

cruises to panama canal

2/24/2007 8:56 pm  
Anonymous Anonymous said...

I had no words to say. I just moved on top of her and hugged her right from top to bottom.
My naked body wanted to feel every inch of her body, and I was caressing her all over like mad.
free tiffany lolita soon began to respond with equal vigor, Her right palm reached my rigid japanese blowjob and began pumping it slowly.
I was so damn horny, but I did not want to waste my semen, just masturbating. I wanted more...I wanted to fuck my cousin there and then.
"Oh free lolita porn...this is too much...I don't think I can keep my promise...please let me remove your panty and let me feel my kiddy sex fuck on your pussy"...I pleaded.
To my utter surprise, without any resistance, free pedo tpg raised her hips, and in a swift action removed her panty.
"You will only feel your pedo russian around my pussy...not inside..OK?" Jenna Jameson Porn insisted.
I almost got angry, and said "OK, but let me play with your tits at least," and moved my pedophile fucking towards her cleavage.
I had no patience to seek her permission. I just pulled her bra straps and and quickly exposed he huge melons.
My mouth instinctly reached her left breast while my right hand was at her right tit. I sucked her like an infant,
expecting to find milk, while my palm was squeezing and kneading her other tit.

2/27/2007 9:46 am  
Anonymous Anonymous said...

viagra online

3/05/2007 10:48 pm  
Anonymous Anonymous said...

She loved her brother so much. He was older than her, 23, and she was just 19. they got along great and did most everything together. free bbs lolita preteens took a year off of school and was going to go away to the collage a few hundred miles away in a big city. Their town was small and Kitty had never lived in a big city. She was scared to move there all by herself. She especially was afraid to lose her brother.
"You aren't losing me, Kitty, I will be right here, right here waiting for you to return. I will call you and write to you if you like..."
She interrupted Jarod,
"Of course I want to keep in touch! I wish dad didn't need your help on the ranch, I wish you could come with me."
free bdsm personals pouted and lowered her head. Her brother, Jarod, lifted it with one finger and smiled,
"If you keep that lip out there a bird might land on it and shit in your mouth..."
They both laughed. She always laughed so much around him. Kitty hugged him tight and he held her close, they both wanted to stay in the moment forever. However, dad called down the stairs and they finished their morning rituals before they went out to take care of the animals.
She was already dressed and was in the bathroom brushing her teeth as her brother got dressed in his room. He took his boxers off while the door was cracked slightly open and Kitty peeked at him between the door to his bedroom and the frame. All she could see as a well toned, tight as hell ass. She had seen him naked when they where younger and experimenting with the world, but he used to be chubby. Now he was sculpted, as was she, from working hard on the ranch.
She ran the toothbrush on her teeth slower as she stared and soon was just standing there sucking on the end of it. He pulled his jeans up and threw on a t-shirt and she backed away into the bathroom to finish. As she was washing her face he came up behind her, pressing his body against her back in order to reach in front of her to get his own toothbrush. His crotch pressed firmly on her ass and she felt a little tingle go through her body. She never thought of it as sexual but it made her a little damp. This was her brother, somebody whom she loved, not a dirty man off the streets bent on getting in her pants. The thought of a twisted stranger trying to fuck her made her smile and her nipples got hard. She was normally a very dirty girl in bed. (and very rarely did she use a bed at all!)
free big tit videos smiled down at his sister while she dried her face and he put toothpaste on his toothbrush. He could smell her free hardcore teen sex, it smelled like strawberries. He loved that smell. Sometimes he would use her shampoo so he could smell strawberries all night. She did the same thing. Kitty would sometimes put a dab of his cologne on her neck so she could smell his scent all night. They never told each other this, or anybody else for that matter. People just wouldn't understand.
They went out early in the morning before breakfast and started chucking hay from a truck into the horse pasture. It was misty out and a loud thunder grew in the hills beyond. It was the beating of many hoofs. A few whinnies and snorts where heard as the horses drew closer. Soon their black outlines where seen galloping and throwing their heads up and down and side to side as they came. Kitty drove the truck off a few yards away from the sinuous mass of pure strength and wild hearts as they closed in on the food. The stallion trotted around the food, watching his mares and foals carefully, then he pushed into the crowd to eat with them. The matriarch of the group was pushing her way in next to the stallion and they nuzzled each other gently then they continued eating.
Kitty and Jarod smiled as they drove off to the barn to clean up the loose hay off the ground that they spilled from the bails. As they worked, Jarod told his sister dirty jokes he read online,
"A guy comes home from work feeling bad about what he had done there. He lays and ponders his actions for a while. A voice in his head tells him, 'it is okay, a lot of doctors have sex with their patience.' He starts to feel a little better then another voice in his head said, 'yes, but you are a veterinarian!'"
They both laughed, though he tried to keep a straight face to add to the humor. Kitty grabbed a handful of loose hay and threw it at him. He ducked and grabbed some of his own, tossing it at her. They laughed and threw hay, getting covered in it and soon she jumped on his back as he went to get more. He spun them both around and they fell to the ground in a pile of the yellow hay laughing and wrestling.
free black sex chat pinned Kitty down under him and they stopped laughing. They where breathing hard and their hearts where pounding. They looked into each other's green eyes and smiled shyly. They had just transformed into virgin lovers, touching the opposite sex for the first time. All the thoughts of being apart drifted away and they where in the moment. Nothing else existed but them, they had each other.
He bent his head down and kissed her softly on the lips. Jarod pulled his head back to make sure she wasn't going to protest and she lifted her free lolitas teenie galleries head up and kissed him back. He slid his hands under her and held her tight as they started kissing heavier, passionately and fervently. Their tongues explored, each in the other's mouth. It was unlike any kiss either of them had ever had. This was pure passion, love and trust.
Jarod moved his hands down and pulled her shirt up, moving his fingers to the front to touch her firm, round, perky tits. Her nipples where rock hard as he touched them. Her breasts where so soft and smooth. Kitty arched her back slightly and slid her own hands up his shirt, feeling his bare chest. He was hot and she could feel his heart pounding, hers was, too. Their hearts thumped away in their chests so hard – like the beating of the wild horse's hooves on the morning damp ground.
They managed to pull each others' shirts off between heavy kisses and he deftly undid her bra from the front clasp. Her tits fell out and her hard nipples stared up at him. He lay his body on top of hers slightly so she could just feel his skin on her nipples. It drove free interracial sex wild. Jarod pressed his hips against hers and pushed his hardening cock into her wet pussy through their pants.
He started to unbutton her jeans as he kissed a path from her lips to her jaw, across her collarbone and between her tits. He licked and sucked each pink nipple, nibbling at times. Then he made his way down further to her tummy and hips. When he got down there he had her pants unbuttoned and pulled halfway down her upper thigh. He kissed and bit her hip bones and looked at her light brown fur patch that lay peeking over the underwear and jeans that he was sliding off.

3/09/2007 11:20 am  
Anonymous Anonymous said...

Ashani shivered against the vampire's touch, still hard, his erection a deep purple almost black. He kept his position and did not move, his entire body shuddering wanting release.
Nikolai rose, adjusting his pants and moving over to an inlaid cabinet to withdraw a small flask. He sipped from it and [url=http://movie-hentai.net/cum_in_pussy_hentai.shtml]cum in pussy hentai[/url] could smell blood...and the rich scent of brandy. "You look so pretty, cat...How do you feel? Be honest."
Ashani blinked trying to get his voice to come to him, "In pain."
Nikolai toasted him and took another drink. "Ah...my poor cat...should I whip you some more? Might that help?" He moved back to the bed, letting some of the stinging brandied-blood run over [url=http://movie-hentai.net/famous_cartoon_sex.shtml]famous cartoon sex[/url]'s pink swollen roseate. "Perhaps take you for a walk? Like this...to the Blushing Glass...let them take turns using that newly found heaven?"
Ashani felt his stomach tighten in fear of being taken in public, anywhere. He knew that he was being teased, his tiger scented a lie. His tiger brushed against his mind, soothing him down. "I do as you tell me."
"Really...sweet tiger? That is good...very good. I do so result to violence when crossed..." Nikolai rubbed his knuckles to the bloated, turgid shaft rising angrily between [url=http://movie-hentai.net/young_hentai.shtml]young hentai[/url]'s legs. He seemed thoughtful, almost meditative of how hard the cat was. Nikolai made a pleased sound, You may go into a kneeling position once more..."
Ashani drew his body up until he was sitting over his calves, his cock jutting out in front of him.
Nikolai sat scant inches from him and gestured with the flask, Touch yourself..."
Ashani used one hand to grasp the base of his cock, holding somewhat tightly to keep himself from spending.
"Faster..." Nikolai murmured, I want to hear it, cat..."
The weretiger began moving his hand up and down his length, almost whimpering as he felt the extreme sensitivity. He kept the pace, his breath coming in very ragged gasps, face drawn taut.
"Mmm...Make it pleasurable cat...do not squeeze so tight...you would tell an inexperienced lover how to touch you, no? And so it shall be...you know the way...You know how to bring yourself..." Nikolai let some of the blood-brandy drip over [url=http://movie-hentai.net/cardcaptor_hentai.shtml]cardcaptor hentai[/url]'s pumping fist, "Show me..."
Ashani swallowed hard and began a slow rhythm, smoothing his fist over his shaft as he drew it away from his body. He pulled at the tip of his cock until it swelled beneath his touch. Drawing back down he slid the blood-brandy over his length, painting it a deep black-red. He bit his lip as he continued the motion, slowly up and quicker down, until his cock was glistening over the tip with his pre-cum.
Nikolai grabbed suddenly at Ashani's collar and pulled him bodily to him. One of his strong pale hands pressed the tiger's chest until Ashani's shoulders touched the bed, his knees remaining on the mattress. Nikolai moved his mouth over the semen and blood-brandied length of the tiger, voraciously sucking at him as if trying to pull his cum forcibly from his swollen balls.
Ashani bit into the sheet, his hands clenched in tight fists as he felt the deft tongue of the vampire playing over him. His shaft jerked within Nikolai's mouth and he felt the vampire's fangs skim over his erection. Ashani groaned loudly into the pillow, wanting to pull back from the vampire or thrust deeper into his throat and spill his seed. He wanted to scream. To cum.
Nikolai felt the rain of Ashani's precum lacing his tongue and slid the tiger into his throat as one long finger delved into Ashani's ass, rubbing that gland wickedly as he milked the tiger. Nikolai's eyes were a drowned red as he looked up to Ashani, and the vampire's voice whispered in his mind, "Cummmmm...."Hentai pics gallery

3/09/2007 2:29 pm  
Anonymous Anonymous said...

In the fourth quarter of this year, [url=http://resanium.com/news/categ-American_cars-1609.html]American cars[/url] plans to have produced 620,000 vehicles (240,000 cars and 380,000 trucks) in the U.S.and Canada.
This is 15,000 units fewer than the previously-announced plan, reflecting the temporary suspension of the Freestar model s production at the Oakville Assembly Plant in Ontario.In the first quarter 2007, the company plans to produce 750,000 vehicles (240,000 cars and 510,000 trucks).In the first quarter 2006, the company produced 876,000 vehicles (316,000 cars and 560,000 trucks).
The company had indicated earlier that first half 2007 production would be 8-12% [url=http://resanium.com/news/categ-American_cars-1609.html]American cars[/url] lower than the first half 2006, and says the first quarter 2007 plan is consistent with the high end of this range.
More view here :
[url=http://resanium.com/news/categ-Auto_Show-338.html] Auto Show [/url]
[url=http://resanium.com/news/categ-AutoSport-98.html] AutoSport [/url]
[url=http://resanium.com/news/categ-Buy_car-1384.html]Buy car[/url]
[url=http://resanium.com/news/categ-Car__Dealers-391.html]Car Dealers[/url]
[url=http://resanium.com/news/categ-Car_classification-261.html]Car classification[/url]
[url=http://resanium.com/news/categ-Car_Finance-89.html]Car Finance[/url]
[url=http://resanium.com/news/categ-Car_Law-601.html]Car Law[/url]
[url=http://resanium.com/news/categ-car_loan-2272.html]car loan[/url]
[url=http://resanium.com/news/categ-Car_New_Models-690.html]Car New Models[/url]
[url=http://resanium.com/news/categ-Car_Parts-390.html]Car Parts[/url]
[url=http://resanium.com/news/categ-Car_Problems-550.html]Car Problems[/url]
[url=http://resanium.com/news/categ-Car_Reviews-3.html]Car Reviews[/url]
[url=http://resanium.com/news/categ-Concept_Cars-392.html]Concept Cars[/url]
[url=http://resanium.com/news/categ-Great_Drives-2642.html]Great Drives[/url]
[url=http://resanium.com/news/categ-In_Gear-2666.html]In Gear[/url]
[url=http://resanium.com/news/categ-New_cars-1414.html]New cars[/url]
[url=http://resanium.com/news/categ-Road_Tests-689.html]Road Tests[/url]
[url=http://resanium.com/news/categ-Sport_Car-844.html]Sport Car[/url]
[url=http://resanium.com/news/categ-Truck_Car-2095.html]Truck Car[/url]
[url=http://resanium.com/news/categ-Used_Cars-503.html]Used Cars[/url]
[url=http://resanium.com/news/categ-Video_Galleries-2490.html]Video Galleries[/url]

3/12/2007 5:42 pm  
Anonymous Anonymous said...

[url=http://flirtbbs.com/]flirt bbs[/url]


3/13/2007 12:24 pm  
Anonymous Anonymous said...


3/25/2007 2:23 pm  
Anonymous Anonymous said...

[url=http://infoeuro.biz/]News around the Europe[/url]

4/07/2007 8:14 am  
Anonymous Anonymous said...

When a car load goes wrong more often then not it happens when the
Finance and Insurance manager prepares a contract for your. Many savings simple
evaporate in that room. Here is the list of things that usually go wrong ...
[url=http://resanium.com/news/categ-car_loan-2272.html]car loan[/url]

4/07/2007 8:53 am  

Post a Comment

Links to this post:

Create a Link

<< Home