Abstract: This thesis explores problems in combinatorial optimization that arise from questions of parametric inference on a variety of statistical models with important applications in computational biology. For statistical models, the goal is to identify the explanations of maximal likelihood for all parametric settings simultaneously. In the case of Markov chains, these maximal probability sequences are known as Viterbi sequences. We prove some combinatorial properties about these Viterbi sequences such as their structures, and we use these properties to derive bounds on the number of Viterbi sequences of length n for k-state Markov chains. Similar results are obtained for other graphical structures such as cycles, toroidal arrays, and fully-observed Markov models. We also investigate the effects of relaxing probabilistic assumptions for parametric inference on statistical models; for instance, we ask what would happen if Markov chains had nonstochastic transition matrices. Finally, the combinatorial object of approximate alignments arises as a simplification in computing optimal alignments of sequence pairs. We enumerate approximate alignments with generating functions and prove unimodality for arrays with 3 rows.