This work covers sequence-based protein homology detection, a fundamental and challenging bioinformatics problem with a variety of real-world applications. The text first surveys a few popular homology detection methods, such as Position-Specific Scoring Matrix (PSSM) and Hidden Markov Model (HMM) based methods, and then describes a novel Markov Random Fields (MRF) based method developed by the authors. MRF-based methods are much more sensitive than HMM- and PSSM-based methods for remote homolog detection and fold recognition, as MRFs can model long-range residue-residue interaction. The text...