Memorial University DAI: An algorithm for finding optimal descent trees in genealogies conditional on the observed data

advanced search

Digital Archives Initiative
Memorial University - Electronic Theses and Dissertations 4

menu off

add document to favorites : add page to favorites : reference url

back to results : previous : next

Search this object:

0 hit(s) :: previous hit : next hit

View:

previous page : next page

Document Description

Title	An algorithm for finding optimal descent trees in genealogies conditional on the observed data
Author	Li, Qiong, 1981-
Description	Thesis (M.Sc.)--Memorial University of Newfoundland, 2010. Mathematics and Statistics
Date	2010
Pagination	xi, 57 leaves : ill.
Subject	Gene mapping--Mathematical models; Genetic genealogy--Mathematical models; Trees (Graph theory);
Degree	M.Sc.
Degree Grantor	Memorial University of Newfoundland. Dept. of Mathematics and Statistics
Discipline	Mathematics and Statistics
Language	Eng
Notes	Includes bibliographical references (leaves 51-57)
Abstract	There are many diseases caused by genes such as cystic fibrosis, hereditary spherocytosis and duchenne muscular dystrophy. Identifying the actual disease-causing genes is important since it may help prevent or avoid genetic disorder. Finding out which genes contribute to diseases is also helpful for understanding why some individuals are more inclined to have physical diseases than others. To do this, we should determine regions of chromosomes that are likely to contain the particular genes responsible for a given human disease. Genetic linkage analysis is developed as a statistical method that allows us to determine these regions of chromosomes. -- Geneticists use pedigrees because they offer many advantages for genetic mapping regardless of the incidence of the genetic disease. One of this advantages is that study of pedigrees is quite powerful if the disease is rare, nevertheless there are many other aspects, like genetic homogeneity, the patterns of transmission, etc. These advantages make the study of pedigrees attractive. However, utilizing such pedigrees in genetic analysis is a computationally challenging task. Time complexity of some algorithms for genetic analysis is exponential in the size of the pedigree. Therefore, it is desirable to find a potentially optimal subpedigree that connects the individuals with the disorder. The aim of this thesis is to study the methods of finding optimal subpedigrees conditional on the observed data in a large pedigree. -- In chapter 1, we first provide background of finding optimal subpedigrees in a large original pedigree problem, in particular, one method to find such subpedigrees that uses graph theory techniques. Then, we introduce some terminologies in graph theory related to the Steiner tree problem. At the end of this chapter, some basic ideas about statistical genetics are provided. -- Chapter 2 concentrates on the description of constructing subpedigrees in a large pedigree based on the Steiner tree problem in graph theory. Two pieces of software, PedHunter and Miniped, that use the Steiner tree algorithm in constructing optimal subpedigrees are introduced. The study in this chapter also enables us to consider the most likely descent trees conditional on the observed data. -- Chapter 3 is devoted to the study of algorithms for finding the most likely descent trees. We first present an algorithm to find the probability of every edge in all possible descent trees, and then reformulate this problem into a directed Steiner tree problem in graph theory. Furthermore, we provide an approximation algorithm to solve this directed Steiner tree problem. -- The final chapter summarizes the results in this thesis and points out some problems for future study.
Type	Text
Resource Type	Electronic thesis or dissertation
Format	Image/jpeg; Application/pdf
Source	Paper copy kept in the Centre for Newfoundland Studies, Memorial University Libraries
Local Identifier	a3475128
Rights	The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission.
Collection	Electronic Theses and Dissertations
Scanning Status	Completed
PDF File	(7.83 MB) -- http://collections.mun.ca/PDFs/theses/Li_Qiong.pdf
CONTENTdm file name	37944.cpd