An Extension to Local Network Alignment using Hidden Markov Models (HMMs)

Abstract

Local alignment is done on biological networks to find common conserved substructures belonging to different organisms. Many algorithms such as PathBLAST (Kelley et al., 2003), Network-BLAST (Scott et al., 2006) are used to align networks locally and they are generally good at finding small sized common substructures. However, these algorithms have same failures about finding larger substructures because of complexity issues. To overcome these issues, Hidden Markov Models (HMMs) is used. The study done by (Qian and Yoon, 2009), uses HMMs to find optimal conserved paths in two biological networks where aligned paths have constant path length. In this paper, we aim to make an extension to the local network alignment procedure done in (Qian and Yoon, 2009) to find common substructures in varying length sizes between the biological networks. We again used same algorithm to find k-length exact matches from networks and we used them to find common substructures in two forms as sub-graphs and extended paths. These structures do not need to have the same number of nodes and should satisfy the predefined similarity threshold (s0). The other parameter is the length of exact paths (k) formed from biological networks and choosing a lower k value is faster but bigger values might be needed in order to balance the number of matching paths below s0.