Applying Lempel-Ziv-Welch to a Genome

Posted in math on June 27th, 2009 by Michæl | No Comments »

What would happen if you were to apply an algorithm designed for Computer Science to Biology? A minor achievement! This program calculates the number of bases different from one genome to another using an LZW dictionary.

sequence

The names of these files are semi self-explanatory, there are three strains of the Rhinovirus, one strain of LI Polyomavirus for comparison, and two ‘modifications’. ‘rhinovirusA.moda’ which has a random base deleted and ‘rhinovirusA.modb’ which has a random base added. As you can see, the score is based on the approximate number of changes to bases (add, or remove) required to convert from one genome to another. I say approximate, and these numbers have decimal points, because the algorithm places a low importance on order, so sequence GTAAAA and AAGTAA would score lower(more similar) then AAGGAA vs AATTAA even though the same number of bases were modified.

The algorithm also doesn’t compare sequences symmetrically. That is to say, if sequence A was compared to dictionary B, the result might be different then if sequence B were compared to dictionary A.

Consider:
Rhinovirus A: 7152 bases
KI Polyomavirus: 5,040 bases
rhinovirusA.txt -> KIpolyomavirus.txt. Score: 105.518803
KIpolyomavirus.txt -> rhinovirusA.txt. Score: -380.504522

As you can see, with 50% more bases, the magnitude of the score more then triples. This error, caused by the fact that the algorithm ignores repetition in the dictionary but not the sequence, is useful for compression, but not so much for biology. I am considering modifications to the formula to remove this error.

While not 100% accurate, it gives a good estimate as to how similar sequences are and its fast to calculate these scores. The process requires less than a second to calculate scores once the dictionary has been created; furthermore, the dictionary doesn’t require a lot of space in memory and it doesn’t need to be calculated for both sequences, only one.

For Team Fortress 2 players…

Posted in News on June 24th, 2009 by Michæl | No Comments »

2009/2010 Lecture Schedule

Posted in Topics that I will only ever cover once on June 24th, 2009 by Michæl | No Comments »

The preliminary 09/10 class schedule was released some time this week. Below is a list of 4th year classes and possible electives.

Fall Required(Security):
(2xTechnical elective, 1xGeneral or Business elective, Capstone if needed)
IT Security Policies & Proced. – 41651 – INFR 4680U
DAVID CHAN
Cap: 50
| University Building A3 UB2050
|_Day: R. 8:10 am – 11:00 am

Fall Technical Electives:
None available yet.

Fall General Electives:

Introductory Sociology – 41626 – SOCI 1000U
Attributes: Liberal Studies – Fac of Eng, Liberal Studies (Science)
X TBAUJ3
| University Pavilion UP1500
|_Day: T. 2:10 pm – 5:00 pm

Science in Context – 40408 – SCIE 1910U
TBA
| University Building A1 UA2140
|_Day: T. 7:10 pm – 10:00 pm

Introductory Psychology – 40424 – PSYC 1000U
Attributes: Liberal Studies – Fac of Eng, Liberal Stds – Energy /Nuclear, Liberal Studies (Science)
X TBAUJ2
| University Pavilion UP1500
|_Day: M. 2:10 pm – 5:00 pm

Political Science – 40422 – POSC 1000U
Attributes: Liberal Studies – Fac of Eng, Liberal Studies (Science)
ROBERT COKE
| University Building A3 UB2080
| Day: T. 12:40 pm – 2:00 pm
|_Day: R. 11:10 am – 12:30 pm
| University Building A1 UA1350
| Day: M. 3:40 pm – 5:00 pm
|_Day: W. 2:10 pm – 3:30 pm

Information Tech for Engineers – 41058 – ENGR 1400U
| JIM CARSWELL
| University Pavilion J102
| Day: M. 11:10 am – 12:30 pm
|_Day: R. 12:40 pm – 2:00 pm

Scientific Computing Tools – 40217 – CSCI 1000U
BRIAN NIXON
Lectures:
| University Building A1 UA1350
|_Day: F. 5:10 pm – 6:30 pm
| University Building A1 UA1350
|_Day: F. 6:40 pm – 8:00 pm
Tutorials:
| University Building A1 UA2230
|_Day: W. 2:10 pm – 4:00 pm
| University Building A1 UA3120
|_Day: R. 5:10 pm – 7:00 pm
| University Building A1 UA2130
|_Day: R. 5:10 pm – 7:00 pm
| University Building A1 UA3130
|_Day: R. 12:10 pm – 2:00 pm
| University Building A1 UA3120
|_Day: W. 5:10 pm – 7:00 pm
| University Building A1 UA2230
|_Day: W. 12:10 pm – 2:00 pm
| University Building A3 UB2058
|_Day: R. 12:10 pm – 2:00 pm
| University Building A3 UB2050
|_Day: W. 11:10 am – 1:00 pm
| University Building A1 UA1220
|_Day: W. 5:10 pm – 7:00 pm

Management of the Enterprise – 40003 – BUSI 1600U
STEVE ROSE
University Building A1 UA1350
|_Day: W. 8:10 am – 11:00 am
|_Day: T. 7:10 pm – 10:00 pm

Winter Required(security):
(1xGeneral, Business, or Technical elective, Capstone if needed)
Cryptography – 71719 – INFR 3600U
MIGUEL VARGAS MARTIN
Cap: 75
Lecture:
| University Building A1 UA2120
|_Day: T. 2:10 pm – 5:00 pm
Tutorial:
| University Building A1 UA2140
|_Day: W. 8:10 am – 11:00 am

IT Forensics – 71722 – INFR 4690U
XIAODONG LIN
Cap: 50
Lecture:
| University Building A1 UA2230
|_Day: T. 8:10 am – 11:00 am
Tutorial:
| University Building A1 UA2220
|_Day: W. 11:10 am – 2:00 pm

Web Service & E-Busi. Security – 71335 – INFR 4660U
PATRICK HUNG
Cap: 30
| University Pavilion J125
|_Day: F. 1:10 pm – 4:00 pm

Winter Technical Elective:
None available yet.

Winter General Electives:

External Environment of Bus – 70311 – BUSI 1650U
Attributes: Liberal Studies (Science)
PRERQ: BUSI 1600 – MANAGEMENT OF THE ENTERPRISE
CUIPING CHEN
| Cap: 200
| University Pavilion UP1500
|_Day: F. 2:10 pm – 5:00 pm
| Cap: 200
| University Pavilion UP1500
|_Day: M. 2:10 pm – 5:00 pm

Impact of Sci. & Tech on Soc. – 70353 – EDUC 1470U
Attributes: Liberal Studies (Science)
| ANTONIE SCHOLTZ
| Cap: 250
| University Building A3 UB2080
|_Day: F. 8:10 am – 11:00 am
| ALYSON KING
| Cap: 250
| University Building A1 UA1350
|_Day: M. 2:10 pm – 5:00 pm

Environmental Science – 70128 – ENVS 1000U
MARY OLAVESON
Lecture:
| Cap: 150
| University Building A1 UA1120
| Day: M. 12:40 pm – 2:00 pm
|_Day: F. 5:10 pm – 6:30 pm
| Cap: 150
| University Building A1 UA1120
| Day: M. 8:10 am – 9:30 am
|_Day: W. 2:10 pm – 3:30 pm
Tutorial:
| University Building A1 UA2220
|_Day: W. 5:10 pm – 7:00 pm
| University Building A1 UA3120
|_Day: R. 8:10 am – 10:00 am
| University Building A1 UA2220
|_Day: R. 2:10 pm – 4:00 pm
| University Building A1 UA3120
|_Day: W. 5:10 pm – 7:00 pm
| University Building A1 UA3140
|_Day: R. 8:10 am – 10:00 am
| University Building A3 UB2058
|_Day: R. 8:10 pm – 10:00 pm
| University Building A3 UB2058
|_Day: T. 5:10 pm – 7:00 pm
| University Building A1 UA3130
|_Day: F. 12:10 pm – 2:00 pm
| University Building A1 UA3120
|_Day: T. 5:10 pm – 7:00 pm
| University Building A1 UA3120
|_Day: M. 5:10 pm – 7:00 pm

Introductory Forensic Science – 70140 – FSCI 1010U
KIMBERLY NUGENT
Cap: 90
| University Pavilion J102
|_Day: W. 3:40 pm – 5:00 pm
| University Pavilion J102
|_Day: F. 2:10 pm – 3:30 pm

Introductory Psychology – 70481 – PSYC 1000U
Attributes: Liberal Studies – Fac of Eng, Liberal Stds – Energy /Nuclear, Liberal Studies (Science)
| Cap: 250
| KIMBERLEY ANN CLOW
| University Building A1 UA1350 Day: T. 2:10 pm – 3:30 pm
|_University Building A1 UA1350 Day: F. 11:10 am – 12:30 pm
| Cap: 250
| AMY LEACH
| University Building A3 UB2080 Day: M. 9:40 am – 11:00 am
|_University Building A1 UA1350 Day: R. 11:10 am – 12:30 pm

Introduction to Social Policy – 70486 – SSCI 1200U
X TBAUJ4
| Cap: 150
| University Building A1 UA1140
| Day: T. 3:40 pm – 5:00 pm
|_Day: R. 12:40 pm – 2:00 pm
| Cap: 150
| University Building A1 UA1140 Day: T. 11:10 am – 12:30 pm
|_University Building A1 UA1120 Day: F. 9:40 am – 11:00 am

Introductory Sociology – 70483 – SOCI 1000U
Attributes: Liberal Studies – Fac of Eng, Liberal Studies (Science)
X TBAUJ3
| Cap: 250
| University Building A3 UB2080
|_Day: W. 7:10 pm – 10:00 pm
| Cap: 250
| University Building A1 UA1350
|_Day: F. 4:10 pm – 7:00 pm
 

Safe Bike Path is Safe

Posted in photos on May 24th, 2009 by Michæl | No Comments »

safepath

Parliament atop the cliff.

Tour: Ottawa

Posted in photos on May 17th, 2009 by Michæl | No Comments »

Random Walk

Posted in News, math on May 12th, 2009 by Michæl | No Comments »

Last year I made a few blog posts about patterns evident in poor pseudorandom number generators. It may be of further interest to my readers that a set of posters has been created on this topic.

park_25
(Source)

African devil pepper

Posted in photos on May 3rd, 2009 by Michæl | No Comments »

African devil pepper, not good to eat.
pepper

Pictures Unrelated

Posted in photos on May 3rd, 2009 by Michæl | No Comments »

Good to know that NASA still has a fax machine.
dscf2989

Somethings fishy.
dscf2990

New meme: X Y with X Z.
dscf2995

So… Does the BBQ not count as food?
dscf2996

I have arrived in Ottawa.

Posted in News on May 1st, 2009 by Michæl | No Comments »

Image – $25 in change – unrelated.

unrelated

Musings on Society

Posted in News on April 22nd, 2009 by Michæl | No Comments »

Ben(TheCarruths) talks about society. I especially like how Part 3 addresses problems with urban planning. You only get once change at urban planning.

Part 1:

Part 2:

Part 3:

Next Page »