Short Abstract: Concentrations of C and G nucleotides in the DNA sequence signify biologically relevant regions as they are often spatially coincident with the promoters of genes. As such these CpG islands, as they are known, are useful predictors of genes. Since 2002, when Takai and Jones introduced a simple software algorithm to predict the location of CpG islands, various alternative algorithms have been introduced to improve the accuracy of these predictions. One algorithm that has gained popularity, the Hidden Markov Model (HMM), identifies whether a given sequence of DNA is in an CpG island state or a background state based on the observation of the sequence of all the nucleotides in the sequence.
The HMM algorithm can be shown to be superior to the Takai and Jones algorithm, but our study indicates that it must be used with caution. The outcome depends very heavily on the initial estimation for transition probabilities from one observation to the next to identify the ‘hidden’ CpG island state. We illustrate this sensitivity to initial conditions, and demonstrates the counter intuitive result that applying the HMM algorithm to two halves of a large segment of DNA does not result in the same predicted number of CpG islands in the two halves as in the combined segments.

Short Abstract: Recent advances in DNA sequencing have made it possible to sequence the whole transcriptome by massively parallel
sequencing, commonly referred as RNA-Seq. RNA-Seq allows to reduce the
sequencing cost and significantly increase data throughput, but it is computationally challenging to use such data for reconstructing full length transcripts and accurately estimate their abundances across all cell types. In this work, we propose a novel statistical “genome-guided” method called “Transciptome Reconstruction using Integer Programing” (TRIP) that incorporates fragment length distribution into novel transcript reconstruction from paired-end RNA-Seq reads. To reconstruct novel transcripts,
we create a splice graph based on exact annotation of exon boundaries and RNA-Seq reads. The exact annotation of exons can be obtained from annotation databases (e.g., Ensembl) or can be inferred from aligned RNA-Seq reads.
We enumerate all maximal paths in the splice graph using a depth-first-search (DFS) algorithm. These paths correspond
to putative transcripts and are the input for the TRIP algorithm.
To solve the transcriptome reconstruction problem we must select a set of putative transcripts with the highest support from the RNA-Seq reads. We formulate this problem as an integer program. The objective is to select the smallest set of putative transcripts that yields a good statistical fit
between the fragment length distribution empirically determined during library preparation and fragment lengths
implied by mapping read pairs to selected transcripts.
Preliminary experimental results on synthetic datasets generated with various sequencing parameters and distribution assumptions show that TRIP has increased transcriptome reconstruction accuracy compared to previous methods that ignore fragment length distribution information.