Abstract
Linkage analysis is a well established method for studying the relationship between the pattern of the occurrence of a given biological trait such as a disease and the inheritance pattern of certain genes in a given family. In this paper we give some improved algorithms for the genetic linkage analysis. In particular we offer an MTBDD based version of these algorithms that turns out to be a considerable improvement of the existing ones both in terms of time and space efficiency. The paper also contains a formal mathematical or computational description of the linkage analysis that gives a deeper insight into the area and therefore a better understanding of the related problems and how to solve them.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aceto, L., Hansen, J.A., Ingólfsdóttir, A., Johnsen, J., Knudsen, J.: The Complexity of Checking Consistency of Pedigree Information and Related Problems. Journal of Computer Science and Technology 19(1), 42–59 (2004); Special issue on bioinformatics (P. Bonazzoni, G.D. Vedova, T.J. guest (ed.))
Abecasis, G.R., Cherny, S.S., Cookson, W.O., Cardon, L.R.: Merlin - rapid analysis of dense genetic maps using sparse gene flow trees. Nature Genetics 30, 97–101 (2001)
Andersen, H.R.: An Introduction to Binary Decision Diagrams, Lecture notes, Technical University of Denmark (1997)
Bahar, R.I., Frohm, E.A., Gaona, C.M., Hachtel, G.D., Macii, E., Pardo, A., Somenzi, F.: Algebraic Decision Diagrams and their Applications. Formal Methods in Systems Design 10(2/3), 171–206 (1997)
Bryant, R.E.: Graph-based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers 8(C-35), 677–691 (1986)
Clarke, E., Fujita, M., McGeer, P., Yang, J., Zhao, X.: Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation. In: International Workshop on Logic Synthesis (1993)
Clarke, E.M., McMillan, K.L., Zhao, X., Fujita, M., Yan, J.C.Y.: Spectral Transforms for Large Boolean Functions with Applications to Technology Mapping. In: 30th ACM/IEEE DAC, Dallas, TX, pp. 54–60 (1993)
Elston, R.C., Stewart, J.: A general model for the genetic analysis of pedigree data. Hum Hered 21, 523–542 (1971)
Cottingham Jr., R.W., Idury, R.M., Schaffer, A.A.: Faster sequential genetic linkage computations. American journal of human genetics 53, 252–263 (1993)
Gudbjartsson, D.F., Jonasson, K., Frigge, M., Kong, A.: Allegro, a new computer program for multipoint linkage analysis. Nature Genetics 25, 12–13 (2000)
Gudbjartsson, D., Hansen, J.A., Ingólfsdóttir, A., Johnsen, J., Knudsen, J.: Single Point Algorithms in Genetic Linkage Analysis. In: Comuter Aided Systems Theory-Eurocast 2003, 9th International Workshop on Computer Aided Systems Theory, Las Palmas de Gran Canaria, Spain, pp. 372–383 (2003)
Ingolfsdottir, A., Gudbjartsson, D., Gunnarsson, G., Thorvaldsson, T.: BDD-Based Algorithms in Genetic Linkage Analysis. In: To appear in the proceedings of NETTAB 2004, Camerino, Italy. LNCS (2004)
Idury, R.M., Elston, R.C.: A Faster and More General Hidden Markov Model Algorithm for Multi Point Calculations. Human Heredity 47, 197–202 (1997)
Kruglyak, L., Daly, M.J., Reeve-Daly, M.P., Lander, E.S.: Parametric and Nonparametric Linkage Analysis: A Unified Multipoint Approach
Kruglyak, L., Lander, E.S.: Faster multipoint linkage analysis using fourier transforms. Journal of Computational Biology 5(1), 7 (1998)
Lange, K.: Mathematical and Statistical Methods for Genetic Analysis. Springer, Heidelberg (1997)
Lander, E.S., Green, P.: Construction of Multilocus enetic Linkage Maps in Humans. Proc. Natl. Acad. Sci. 84, 2363–2367 (1987)
Kruglyak, L., Daly, M.J., Reeve-Daly, M.P., Lander, E.S.: Parametric and nonparametric linkage analysis: a unified multipoint approach. Am. J. Hum. Genet. 58, 1347–1363 (1996)
Markianos, K., Daly, M.J., Kruglyak, L.: Efficient multipoint linkage analysis through reduction of inheritance space. American journal of human genetics 68, 963–977 (2001)
Ott, J.: Analysis of Human Genetic Linkage, 3rd edn. The Johns Hopkins University Press, Baltimore (1999)
Somenzi, F.: CUDD: CU decision diagram package. In: Public software. Colorado University, Boulder (1997)
O’Connell, J.R.: Rapid Multipoint Linkage Analysis via Inheritance Vectors in the Elston-Stewart Algorithm. Hum Hered 51, 226–240 (2001)
[RJ86] Rabiner, L.R., Juang, B.H.: An introduction to hidden Markov models. IEEE ASSP Magazine, 4–6 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ingolfsdottir, A., Gudbjartsson, D. (2005). Genetic Linkage Analysis Algorithms and Their Implementation. In: Priami, C., Merelli, E., Gonzalez, P., Omicini, A. (eds) Transactions on Computational Systems Biology III. Lecture Notes in Computer Science(), vol 3737. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11599128_9
Download citation
DOI: https://doi.org/10.1007/11599128_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30883-6
Online ISBN: 978-3-540-31446-2
eBook Packages: Computer ScienceComputer Science (R0)