In this thesis, we attempt to find approximately repeating patterns in DNA called motifs by modeling the problem both as a maximum edge weight clique problem (MEWCP) and as a maximum a posteriori inference on a Markov random field (MAP-MRF). Though we simplify this motif discovery problem as an ungapped sequence alignment with a known motif length, we make up for this simplification by generating multiple solutions. We implement three different approaches: an integer linear programming formulation approach and a branch-and-bound approach for the MEWCP model, and a loopy belief propagation approach for the MAP-MRF model. We test our approaches by trying to find the motifs of Eschericha coli sequence data. Through motif discovery, we also make a connection between the MEWCP and MAP-MRF, and thus make a connection between any approach used to solve one graph model to any approach used to solve the other graph model.