|
A Formalization of Linkage Analysis
Anna Ingólfsdóttir
February 2002 |
Abstract:
In this report a formalization of genetic linkage analysis is
introduced. Linkage analysis is a computationally hard biomathematical
method, which purpose is to locate genes on the human genome. It is rooted in
the new area of bioinformatics and no formalization of the method has
previously been established. Initially, the biological model is presented. On
the basis of this biological model we establish a formalization that enables
reasoning about algorithms used in linkage analysis. The formalization
applies both for single and multi point linkage analysis. We illustrate the
usage of the formalization in correctness proofs of central algorithms and
optimisations for linkage analysis. A further use of the formalization is to
reason about alternative methods for linkage analysis. We discuss the use of
MTBDDs and PDGs in linkage analysis, since they have proven efficient for
other computationally hard problems involving large state spaces. We conclude
that none of the techniques discussed are directly applicable to linkage
analysis, however further research is needed in order to investigated whether
a modified version of one or more of these are applicable
Available as PostScript, PDF. |