טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentFishelson Ma'ayan
SubjectEfficient Genetic Linkage Computations for General Pedigrees
DepartmentDepartment of Computer Science
Supervisor Professor Dan Geiger


Abstract

Genetic linkage analysis is a useful statistical tool for associating functionality of genes to their location on the chromosome.  As the genome project progressed and more DNA markers became available, multipoint linkage analysis has become an integral part of mapping disease genes and constructing genetic maps. In this thesis, we present algorithms for performing exact multipoint likelihood calculations and maximum likelihood haplotyping on general pedigrees with a large number of highly polymorphic markers, taking into account a variety of disease models. We have implemented these algorithms in a new computer program called Superlink which outperforms most leading linkage software with regards to functionality, speed, memory requirements and extensibility. The efficiency of our algorithms stems from the internal representation of linkage analysis problems as Bayesian networks. Using this representation allows efficient handling of a wide variety of linkage problems, by choosing the elimination order automatically according to the linkage problem at hand. We also define a refined optimization problem behind the main computational step in likelihood computations and haplotyping analysis. This problem, called the constrained elimination problem, deals with finding an efficient elimination order, namely, an efficient order of marginalization and combination operations.  We present several heuristic algorithms that seek optimized solutions to this problem. The presented algorithms can also be utilized in a variety of other applications, such as: constraint satisfaction, dominating set, graph K-colorability, and Hamiltonian circuit, as well as in other applications of Bayesian networks. Experimental results that demonstrate the performance of Superlink and compare between Superlink and other leading linkage programs are presented.  Also presented, are experimental results that demonstrate the performance of our heuristic algorithms for solving the constrained elimination problem.  We conclude by presenting several mapping studies in which Superlink has been used.