This thesis focuses on the application of Monte Carlo methods to solving problems in bioinformatics. More specifically, we want to be able to translate biological, genomic, and proteomic problems into mathematical problems by modeling them using discrete state-space hidden Markov models. Unknown parameters are modeled with prior distributions, and are estimated jointly with the unknown states. Depending on the type of problem, the model can also be formulated in a batched or sequential manner. We will show that in most cases, even when the problem is batched in nature, the sequential approach will provide better performance, and more efficient in terms of computational complexity. In this thesis, we will present applications of this methodology to problems such as DNA sequence base-calling, discovery of motifs in DNA sequences, phasing of haplotypes for diploid organisms, and the prediction of secondary structure for proteins based on amino acid sequences.