  Pair Hidden Markov Models (PHMMs) are probabilistic models used for pairwise
sequence alignment, a quintessential problem in bioinformatics. PHMMs include
three types of hidden states: match, insertion and deletion. Most previous
studies have used one or two hidden states for each PHMM state type. However,
few studies have examined the number of states suitable for representing
sequence data or improving alignment accuracy.We developed a novel method to
select superior models (including the number of hidden states) for PHMM. Our
method selects models with the highest posterior probability using Factorized
Information Criteria (FIC), which is widely utilised in model selection for
probabilistic models with hidden variables. Our simulations indicated this
method has excellent model selection capabilities with slightly improved
alignment accuracy. We applied our method to DNA datasets from 5 and 28
species, ultimately selecting more complex models than those used in previous
studies.
