Ed's Big PlansIf I had a little more time… ISC 2010
Brief: I encourage anyone who wants to play to do so– this is the second year that the Intelligent Systems Challenge has existed. If I had a little more time and a team, I’d do this 
Registration has still yet to open so go read up on natural language processing and state failures.
Matthew‘s part of a team that’s participating again this year 
Irony is tough.
Irony should be easier to deploy. It should have a generic-like type signature, so we know how to use it flawlessly each time.
Irony i<Notion, Meaning, Alternative> = new Irony<Notion, Meaning, Alternative>();
Neighbor Joining Revisited
Brief: It’s been such a long time since I’ve actually implemented neighbor joining for any reason– The neighbor-joining method (Saitou N, Nei M. 1987) is used to create binary trees such that we iteratively merge pairs of most-similar points in a collection. Every merge results in the creation of a new node where it adopts the two merged nodes as its children. This occurs until there is only one node left. This single remaining node is the root of the tree. Here it is on wikipedia, wherein a transitional Q-Matrix is used to store intermediate values– and here it is care of Fred Opperdoes, explained using a net divergence array and a distance matrix. The algorithm described is identical, but Opperdose’s explanation is a lot faster to comprehend. … Incidentally, the wikipedia article doesn’t explain how to break the tie to decide which child node gets what value against their newly merged parent. In wikipedia’s formalization, one gets a pair of children of the same distance from the parent but one has a negative sign (this is incorrectly ambiguous); in both worked examples however, the actual (correct) score of one arbitrary child is equal to the difference between the score of the parent and the other child. In reality, the steps following treat the two children symmetrically anyway, so which one is one and which the other is trivial… there is no favourite child– and barring the above error, no negative child either.
Practical Scripting for Biologists (Python)
Draft Syllabus Here (public Google doc).
I’m currently putting together the course materials for my Python Crash Course for Biologists… all that’s left is to fasten the lesson ideas into slide shows, example code and exercise materials and I’ll be ready to indicate a launch date.
I’ve heard some interest from iGem members, lab mates here at the Meiering lab and also the Waterloo Bioinformatics Club… I want to run this soon.
Andre may be doing something similar on a different topic– so it’s been very nice to have another set of eyes evaluate the syllabus.
WordPress Inline Comments
Thanks to flisterz for this tip!
I added inline comments to this blog– it actually involves editing index.php, something I generally avoided doing. Peering into the code, it’s as normal as any other PHP so all of those silly worries were washed aside. The WordPress Codex does an excellent job of — well, it’s an incomplete API reference so it at the very least lists the functions that exist if it doesn’t truly explain them all.
Anyway– I didn’t just copy the hint from flisterz one to one because I wanted different functionality– but it did offer an example that let me make my changes much more easily. Because I don’t get very many comments, I don’t mind having complete comments show up inline on the main page instead of just an excerpt. As well, I wanted to have nice title bars to separate out the comments too… finally, while I was mucking around in the code, I decided to move the post tags up right beneath the title of each post instead of at the very bottom.
Changes made are inside index.php located before <?php end_while() ?>, just as in flisterz’s tip– here’s my version.
<div class="recent-comment">
<?php $comment_array = get_approved_comments($wp_query->post->ID); ?>
<?php if ($comment_array) { ?>
<?php foreach($comment_array as $comment){ ?>
<br />
<div style="background-color: #DDD9C6; border: 1px #F2EFE5 solid;">
<em><?php comment_author_link(); ?> says...</em>
</div><div>
<?php comment_text(); ?>
</div>
<?php } ?>
<?php } ?>
</div>
In future, I’ll probably want to clean up the markup a bit by moving the style changes to this theme’s CSS. Oh, while I’m at it, I should also thank Digital Nature for this awesome theme (Arclite).
fridgelib — Andre’s C Library
Brief: Fridge Library (fridgelib) is a light weight C library that’s basically what each C programmer eventually comes away with. Fridgelib contains a queue, stack and trie data type implementation– these implementations are cleaner than mine, hence I have devoured them into my code where necessary.
There is however one item that Andre’s told me I can add to fridgelib if I can ever tidy it up, and that’s my evil linked-array. It’s basically a doubly linked list whose elements are arrays of fixed size; the traversal is cut down by a multiple of that array size while indexing thereafter is still constant time given the modulus of the index. My evil implementation is a double-headed stack/queue/array which supported python-like negative-value indexing, slicing and iteration… actually, that’s when I decided it had grown too grotesque and left it to sit in my repository…
I’ll probably return to it later, to remove slicing and to more cleanly define the semantics of iteration.
Hmm– the only things that are really missing from fridgelib are the hashtable and either a nice red-black tree or a treap…
Yo! Holy crap you have a blog. Interesting concept of a linked array. Do the allocations increase exponentially? You would have an interesting problem trying to keep constant time because even if your allocations increase exponentially, if you have a large number, you would have to traverse the small nodes first.
No, the allocations increase at a constant size
The modulus short cut can only work that way– this pseudocode should clear it up… I haven’t checked for off-by-one logical errors– this’ll give you the sense of what I’m doing though.
Pseudocode:
function get linkedArray this, int index:
int which_page = index / length of one internal array
int which_index_in_page = index % length of one internal array
internalArray this_page = this -> start
for int i = 0; i < which_page; i++
this_page = this_page ->> next
return this_page -> array[ which_index_in_page ]
struct linkedArray:
int length of one internal array
internalArray start
struct internalArray:
generic array
internalArray next
Note that I haven’t added anything in the above to convert out of Python-style negative-indices– I also had an optimization that would traverse the list of arrays from the last internal array instead of the first internal array if the selected index is actually on a ‘page’ that’s past the midpoint of the list.
Edit: Getting pseudocode in html to work well in WordPress comments is a pain…
Hmm, if you double the number and start the array size at 1, the capacity:
sum of 1->numPages 2**maxIndex
You could either do a O(lg(maxIndex)) (using bit shifting) access if you don’t store where all the pages start, or a O(1) access if you do. It’s an extra 4 bytes per page plus the occasional expansion of the index which should happen seldomly. That way inserts are no longer a max O(numberInserted/number per array) but O(lg(numberInserted)).
Heavier on the memory but saves big time on write time. I like this idea though, never heard of a linked array. Arbitrary inserts aren’t so bad because you can just expand one array rather than all of them, that’s so smart!
I suppose though, if you knew that the inserts were constant, then your data structure would be better. It really does depend on application.
