Snowdays

Those who live on the south of the England, will no doubt be aware of the abundance of white stuff which deposited itself at the begining of this week.

I thought I'd share with you a few fantastic photos taken by my good friend Phil around the University of Reading.

Sudoku Genetic Algorithm: Introduction

What Is Sudoku?

Sudoku is a recently introduced, Japanese number puzzle where the objective is to fill a 9x9 grid so that each row, column, and 3x3 sub grid, contains numbers 1 through 9. The grids are usually partially filled and so it's the job of the solver to complete the remaining empty cells, without violating these. Sudoku problems range from easy to hard, where easy grids have more than one possible solution, and hard, where the grids have only one unique solution.

Sudoku puzzle with solution numbers marked in red. Source: Wikipedia

Why Use A Genetic Algorithm?

...because curiosity killed the cat, that's why!

Genetic Algorithms to which I'll now abbreviate to GA, is an interesting means to solving a problem. Though in this domain, they certainly don't provide a performance increase, they're often used in engineering to solve problems to which the solution space is so vast, there exists no algorithmic approach and Monte Carlo methods simply skim the surface of all possible solutions.

Gross Over-Simplification:

We maintain a population of ideally diverse solutions, to which each individuals fitness (effectiveness of solving a given problem) is evaluated. The highest ranking individuals are chosen to seed the next generation, with low ranking individuals discarded. This process repeats until some given threshold has been breached. This process effectively refines good solutions in an attempt to increase their fitness, so much so that they solve the problem. Note that this is a Gross Over-Simplification and much work goes into the degree of seeding, mutating solutions and even the evaluation function... GAs are not a one-stop-shop to solve world hunger.

In general, we use a GA to solve Sudoku puzzles because we can and it provides a more holistic approach to solving a problem.

In this series of posts, we'll explore the various aspects of implementing a Sudoku GA including the pitfalls and misconceptions of GAs in general.

Shiny Workspace...

Recently I took the plunge and ordered my new PC with the aim to provide a powerful enough sandbox for CUDA development etc. Unfortunately, my vanity took over and spent a bit more than I should of done on the aesthetics (relative to what I would've payed).

For those of us who appreciate this stuff and will find it meaningful, here are the specs.

• AMD Phenom Quad-core 9950 Black Edition
• OCZ 4 GB DDR2 @ 1066MHz
• Samsung SpinPoint F1 HD103UJ 1TB Hard Drive SATAII with 32MB Cache
• MSI K9N2 Diamond nForce 780a SLI Socket AM2+
• BFG GTX280 OC2 Edition 1GB
  Currently returned to supplier due to getting hot enough to cook breakfast on within 10 seconds of running 3D Mark 06.
  
• Antec Fusion MAX VERIS Black ATX Media Center Case

Many of the people I've spoken to about my choice of processor and memory, responded with either distain or mostly 'you could've done better' kind of attitude. Let me take the opportunity to explain myself:

1. I brought an AMD processor because all my previous processors have been Intel and I fancied a change irrespective of marginal performance losses.
2. The memory was DDR2 because most the DDR3 mainboards are hideously expensive and you don't get many 'nice' extras with them. My choice of mainboard enabled me to have a high-end Nvidia chipset with a Creative Sound-Blaster X-Fi bundled in.
   

The rest of the components require no justification.

Empty Designs

As a massive proponent of minimalist design, I came across this article today on Smashing Magazine... stick it in your inspiration scapbook!

Introduction to Phylogenetics: Preface

Series Contents

1. Introduction to Phylogenetics: Preface
2. Introduction to Phylogenetics Part I: Evolutionary Model
3. Introduction to Phylogenetics Part II: Stationary Probabilities of Mutation
4. Introduction to Phylogenetics Part III: Phylogenetic Construction by Maximum Likelihood
5. Introduction to Phylogenetics Part IV: Multiple Sequence Alignments
6. Introduction to Phylogenetics Appendix A: Entrez SOAPing
7. Introduction to Phylogenetics Appendix B: CUDA in C#
8. Introduction to Phylogenetics Appendix C: CUDA Optimisation

In this series of posts, I'm going to give the surface of bioinformatics a good scratching, written from the perspective of a non-biologist. The main focus is to implement many of the algorithms we'll encounter in this area, in parallel, or more specifically in CUDA.NET. During the journey I'll add code snipets where possible either in a specific language or in pseudocode. Pop over to Google Code to grab the latest version of the source which much of the research in this area has led to.

Introduction to Phylogenetics Part I: Evolutionary Model

Series Contents

1. Introduction to Phylogenetics: Preface
2. Introduction to Phylogenetics Part I: Evolutionary Model
3. Introduction to Phylogenetics Part II: Stationary Probabilities of Mutation
   
4. Introduction to Phylogenetics Part III: Phylogenetic Construction by Maximum Likelihood
5. Introduction to Phylogenetics Part IV: Multiple Sequence Alignments
   
6. Introduction to Phylogenetics Appendix A: Entrez SOAPing
7. Introduction to Phylogenetics Appendix B: CUDA in C#
   
8. Introduction to Phylogenetics Appendix C: CUDA Optimisation

Introduction

For constructing a phylogenetic tree based on DNA data, we need to have an idea of the evolutionary trends or how specific bases mutated over time. It is likeley that with high evolutionary rates result a tree with short branches will be produced, low evolutionary rates would result in a tree with long branches. Evolutionary models which don't impose an equal probability of mutation on all bases (not unlike the Jukes-Cantor model), require some parameters on the likelihood of such a mutation.


Scope of Article

Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Proin in ante in sapien placerat accumsan. Sed non turpis nec ipsum dapibus molestie. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Donec sem neque, gravida sed, dapibus a, laoreet quis, justo. Ut semper neque vel ligula. In placerat consequat dui. Praesent consectetuer feugiat metus. Phasellus consequat semper diam. Suspendisse massa. Praesent vel risus. Donec sodales posuere risus. Donec scelerisque ante sagittis erat. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Morbi vitae lectus sit amet nisi ultricies ullamcorper. Duis lobortis. Aenean dignissim risus sit amet sem. Donec mollis diam id est. Vestibulum pulvinar leo id diam.

Predicting Evolution

We construct a Markov Chain representing all possible changes of state DNA can undergo (a generalized model is shown below). The assumption of a constant rate of change is heavily tied to the concept of a molecular clock and is highly contraversial. The idea that evolution occurs at a constant rate is a gross oversimplification of the process but to ease computation and also generate a sense of direction, it is often inherant in phylogenetic reconstruction.

Figure I -Markov Chain representing the change of states for all bases of DNA

Jukes-Cantor Model

Developed in 1969, is the simplest evolutionary model, available in descrete and continuous time flavours. The model assumes a constant rate of evolution which remain equal for all bases.


Kimura Model

Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Proin in ante in sapien placerat accumsan. Sed non turpis nec ipsum dapibus molestie. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Donec sem neque, gravida sed, dapibus a, laoreet quis, justo. Ut semper neque vel ligula. In placerat consequat dui. Praesent consectetuer feugiat metus. Phasellus consequat semper diam. Suspendisse massa. Praesent vel risus. Donec sodales posuere risus. Donec scelerisque ante sagittis erat. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Morbi vitae lectus sit amet nisi ultricies ullamcorper. Duis lobortis. Aenean dignissim risus sit amet sem. Donec mollis diam id est. Vestibulum pulvinar leo id diam.


HKY Model
Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Proin in ante in sapien placerat accumsan. Sed non turpis nec ipsum dapibus molestie. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Donec sem neque, gravida sed, dapibus a, laoreet quis, justo. Ut semper neque vel ligula. In placerat consequat dui. Praesent consectetuer feugiat metus. Phasellus consequat semper diam. Suspendisse massa. Praesent vel risus. Donec sodales posuere risus. Donec scelerisque ante sagittis erat. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Morbi vitae lectus sit amet nisi ultricies ullamcorper. Duis lobortis. Aenean dignissim risus sit amet sem. Donec mollis diam id est. Vestibulum pulvinar leo id diam.


Felsenstein Model

Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Proin in ante in sapien placerat accumsan. Sed non turpis nec ipsum dapibus molestie. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Donec sem neque, gravida sed, dapibus a, laoreet quis, justo. Ut semper neque vel ligula. In placerat consequat dui. Praesent consectetuer feugiat metus. Phasellus consequat semper diam. Suspendisse massa. Praesent vel risus. Donec sodales posuere risus. Donec scelerisque ante sagittis erat. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Morbi vitae lectus sit amet nisi ultricies ullamcorper. Duis lobortis. Aenean dignissim risus sit amet sem. Donec mollis diam id est. Vestibulum pulvinar leo id diam.

---

References

1. Ewens W. J., Grant G. R., Statistical Methods in Bioinformatics, Springer 2005