Genome Assemblies and Interval Graphs
Martin Farach-Colton, The Sequence Assembly Problem is the computation end of the Human Genome Project (HGP). After individual chromosomal fragments are sequenced in the laboratory, the complete sequence of the genome must be assembled from the constituent parts. It is therefore one of the fundamental problems of bioinformatics. The HGP started out with one general approach to sequencing (Hierarchical Shotgun Sequencing) and changed to another (Clone-based Sequencing). Both methods rely on similar mathematics related to interval graphs. However, the differences are crucial. We explore some of the implications of this change in sequencing technology. We present Barnacle, a method for assembling clone-based sequences and compare it with the NCBI assembler used for the official NIH assembly.
Return to homepage.
The second and fourth
images
in the header are courtesy the BIODIDAC website. |