A Formalization of Linkage Analysis

Anna Ingolfsdottir, A.I. Christensen, Jens A. Hansen, J. Johnsen, John Knudsen, Jacob Illum Rasmussen

Research output: Book/ReportBookResearch

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
Original languageEnglish
Place of PublicationÅrhus
PublisherBRICS - Aarhus University
Publication statusPublished - 2002
SeriesB R I C S Report Series
NumberRS-02-7

Cite this

Ingolfsdottir, A., Christensen, A. I., Hansen, J. A., Johnsen, J., Knudsen, J., & Rasmussen, J. I. (2002). A Formalization of Linkage Analysis. Århus: BRICS - Aarhus University. B R I C S Report Series, No. RS-02-7
Ingolfsdottir, Anna ; Christensen, A.I. ; Hansen, Jens A. ; Johnsen, J. ; Knudsen, John ; Rasmussen, Jacob Illum. / A Formalization of Linkage Analysis. Århus : BRICS - Aarhus University, 2002. (B R I C S Report Series; No. RS-02-7).
@book{92db6eb0003211dab4d5000ea68e967b,
title = "A Formalization of Linkage Analysis",
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",
author = "Anna Ingolfsdottir and A.I. Christensen and Hansen, {Jens A.} and J. Johnsen and John Knudsen and Rasmussen, {Jacob Illum}",
year = "2002",
language = "English",
series = "B R I C S Report Series",
number = "RS-02-7",
publisher = "BRICS - Aarhus University",

}

Ingolfsdottir, A, Christensen, AI, Hansen, JA, Johnsen, J, Knudsen, J & Rasmussen, JI 2002, A Formalization of Linkage Analysis. B R I C S Report Series, no. RS-02-7, BRICS - Aarhus University, Århus.

A Formalization of Linkage Analysis. / Ingolfsdottir, Anna; Christensen, A.I.; Hansen, Jens A.; Johnsen, J.; Knudsen, John; Rasmussen, Jacob Illum.

Århus : BRICS - Aarhus University, 2002. (B R I C S Report Series; No. RS-02-7).

Research output: Book/ReportBookResearch

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 -

Ingolfsdottir A, Christensen AI, Hansen JA, Johnsen J, Knudsen J, Rasmussen JI. A Formalization of Linkage Analysis. Århus: BRICS - Aarhus University, 2002. (B R I C S Report Series; No. RS-02-7).