Using Interval Graphs for Solving Map Assembly Problems
James Ryder Randall · Library and Archives Canada (Government of Canada) · 1997
This thesis is concerned with graph theory-based algorithms to handle the genetic map assembly problem. These algorithms are designed to build the genetic maps using only graph theoretical properties so as to better understand how much information can be obtained from the graph structure. In particular, several algorithms are developed using ideas from interval graphs and the asteroidal triple-free graphs. The core of the problem is dealing with the noise present in the data. This noise can be split into two different categories: false negatives (edges removed from a graph), and false positives (edges added to a graph). For the case of noise introduced as a result of false negatives, lexicographic breadth-first search is used to produce useful orderings even under heavy noise conditions. Three different algorithms are developed for dealing with false positives. The algorithms can detect the effects of false positives, but none are effective in removing this type of noise.