TY - BOOK
T1 - A Formalization of Linkage Analysis
AU - Ingolfsdottir, Anna
AU - Christensen, A.I.
AU - Hansen, Jens A.
AU - Johnsen, J.
AU - Knudsen, John
AU - Rasmussen, Jacob Illum
PY - 2002
Y1 - 2002
N2 - 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
AB - 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
M3 - Book
T3 - B R I C S Report Series
BT - A Formalization of Linkage Analysis
PB - BRICS - Aarhus University
CY - Århus
ER -