The Use of Maximum Edge Weight Clique and Markov Random Field Problem Formulation to Discover Motifs

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.

Creator: 

Kravchuk, Alexandra

Date: 

2021

Abstract: 

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.

Subject: 

Mathematics
Bioinformatics

Language: 

English

Publisher: 

Carleton University

Thesis Degree Name: 

Master of Science: 
M.Sc.

Thesis Degree Level: 

Master's

Thesis Degree Discipline: 

Mathematics

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).