More Web Proxy on the site http://driver.im/

article

TreeDT: Tree Pattern Mining for Gene Mapping

Authors:

Hannu Toivonen,

Vesa OllikainenAuthors Info & Claims

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 3, Issue 2

Pages 174 - 185

https://doi.org/10.1109/TCBB.2006.28

Published: 01 April 2006 Publication History

Abstract

We describe TreeDT, a novel association-based gene mapping method. Given a set of disease-associated haplotypes and a set of control haplotypes, TreeDT predicts likely locations of a disease susceptibility gene. TreeDT extracts, essentially in the form of haplotype trees, information about historical recombinations in the population: A haplotype tree constructed at a given chromosomal location is an estimate of the genealogy of the haplotypes. TreeDT constructs these trees for all locations on the given haplotypes and performs a novel disequilibrium test on each tree: Is there a small set of subtrees with relatively high proportions of disease-associated chromosomes, suggesting shared genetic history for those and a likely disease gene location? We give a detailed description of TreeDT and the tree disequilibrium tests, we analyze the algorithm formally, and we evaluate its performance experimentally on both simulated and real data sets. Experimental results demonstrate that TreeDT has high accuracy on difficult mapping tasks and comparisons to other methods (EATDT, HPM, TDT) show that TreeDT is very competitive.

References

[1]

{1} P. Sevon, H.T.T. Toivonen, and V. Ollikainen, "TreeDT: Gene Mapping by Tree Disequilibrium Test," Proc. ACM SIGKDD Int'l Conf. Knowledge Discovery and Data Mining, pp. 365-370, 2001.

Digital Library

[2]

{2} R. Miller, Simultaneous Statistical Inference. New York: McGraw-Hill, 1966.

[3]

{3} P. Westfall and S. Young, Resampling-Based Multiple Testing: Examples and Methods for p-Value Adjustment. New York: Wiley, 1993.

[4]

{4} D. Knuth, The Art of Computer Programming, Volume III--Sorting and Searching. Reading, Mass.: Addison-Wesley, 1975.

Digital Library

[5]

{5} B. Devlin, N. Risch, and K. Roeder, "Disequilibrium Mapping: Composite Likelihood for Pairwise Disequilibrium," Genomics, vol. 36, pp. 1-16, 1996.

[6]

{6} L. Lazzeroni, "Linkage Disequilibrium and Gene Mapping: An Empirical Least-Squares Approach," Am. J. Human Genetics, vol. 62, pp. 159-170, 1998.

[7]

{7} M. McPeek and A. Strahs, "Assessment of Linkage Disequilibrium by the Decay of Haplotype Sharing, with Application to Fine-Scale Genetic Mapping," Am. J. Human Genetics, vol. 65, pp. 858-875, 1999.

[8]

{8} S. Service, D. Temple Lang, N. Freimer, and L. Sandkuijl, "Linkage-Disequilibrium Mapping of Disease Genes by Reconstruction of Ancestral Haplotypes in Founder Populations," Am. J. Human Genetics, vol. 64, pp. 1728-1738, 1999.

[9]

{9} J. Terwilliger, "A Powerful Likelihood Method for the Analysis of Linkage Disequilibrium between Trait Loci and One Ore More Polymorphic Marker Loci," Am. J. Human Genetics, vol. 56, pp. 777- 787, 1995.

[10]

{10} A. Morris, J. Whittaker, and D. Balding, "Bayesian Fine-Scale Mapping of Disease Loci, by Hidden Markov Models," Am. J. Human Genetics, vol. 67, pp. 155-169, 2000.

[11]

{11} A. Morris, J. Whittaker, and D. Balding, "Fine-Scale Mapping of Disease Loci via Shattered Coalescent Modelling of Genealogies," Am. J. Human Genetics, vol. 70, pp. 686-707, 2002.

[12]

{12} B. Rannala and J. Reeve, "High-Resolution Multipoint Linkage-Disequilibrium Mapping in the Context of Human Sequence," Am. J. Human Genetics, vol. 69, pp. 159-178, 2001.

[13]

{13} J. Lam, K. Roeder, and B. Devlin, "Haplotype Fine-Mapping by Evolutionary Trees," Am. J. Human Genetics, vol. 66, pp. 659-673, 2000.

[14]

{14} R. Spielman, R. McGinnis, and W. Ewens, "Transmission Test for Linkage Disequilibrium: The Insulin Gene Region and Insulin-Dependent Diabetes Mellitus (IDDM)," Am. J. Human Genetics, vol. 52, pp. 506-516, 1993.

[15]

{15} L. Kruglyak, M. Daly, M. Reeve-Daly, and E. Lander, "Parametric and Nonparametric Linkage Analysis: A Unified Multipoint Approach," Am. J. Human Genetics, vol. 58, pp. 1347-1363, 1996.

[16]

{16} S. Lin, A. Chakravarti, and D. Cutler, "Exhaustive Allelic Transmission Disequilibrium Tests as a New Approach to Genome-Wide Association Studies," Nature Genetics, vol. 36, pp. 1181-1188, 2004.

[17]

{17} H. Toivonen, P. Onkamo, K. Vasko, V. Ollikainen, P. Sevon, H. Mannila, M. Herr, and J. Kere, "Data Mining Applied to Linkage Disequilibrium Mapping," Am. J. Human Genetics, vol. 67, pp. 133- 145, 2000.

[18]

{18} H. Toivonen, P. Onkamo, K. Vasko, V. Ollikainen, P. Sevon, H. Mannila, and J. Kere, "Gene Mapping by Haplotype Pattern Mining," Proc. IEEE Int'l Symp. Bio-Informatics and Biomedical Eng., pp. 99-108, 2000.

Digital Library

[19]

{19} P. Onkamo, V. Ollikainen, P. Sevon, H. Toivonen, H. Mannila, and J. Kere, "Association Analysis for Quantitative Traits by Data Mining: QHPM," Annals of Human Genetics, vol. 66, pp. 419-429, 2002.

[20]

{20} P. Sevon, H. Toivonen, and P. Onkamo, "Gene Mapping by Pattern Discovery," Data Mining in Bioinformatics, J. Wang, M. Zaki, H. Toivonen, and D. Shasha, eds., Springer, 2005.

[21]

{21} D. Qian, "Haplotype Sharing Correlation Analysis Using Family Data: A Comparison with Family-Based Association Test in the Presence of Allelic Heterogeneity," Genetic Epidemiology, vol. 27, pp. 43-52, 2004.

[22]

{22} K. Yu, C. Gu, M. Province, C. Xiong, and D. Rao, "Genetic Association Mapping under Founder Heterogeneity via Weighted Haplotype Similarity Analysis in Candidate Genes," Genetic Epidemiology, vol. 27, pp. 182-191, 2004.

[23]

{23} J. Tseng, "Evolutionary-Based Grouping of Haplotypes in Association Analysis," Genetic Epidemiology, vol. 28, pp. 220-231, 2005.

[24]

{24} Y. Ge, S. Dudoit, and T. Speed, "Resampling-Based Multiple Testing for Microarray Data Analysis," TEST, vol. 12, pp. 1-77, 2003.

[25]

{25} R. Hudson, "Generating Samples under a Wright-Fisher Neutral Model," Bioinformatics, vol. 18, pp. 337-338, 2002.

[26]

{26} S. Lin, A. Chakravarti, and D. Cutler, "Haplotype and Missing Data Inference in Nuclear Families," Genome Research, vol. 14, pp. 1624-1632, 2004.

[27]

{27} S. Bain, J. Todd, and J. Barnett, "The British Diabetic Association-Warren Repository," Autoimmunity, vol. 7, pp. 83-85, 1990.

[28]

{28} D. Qian and L. Beckmann, "Minimum-Recombinant Haplotyping in Pedigrees," Am. J. Human Genetics, vol. 70, pp. 1434-1445, 2002.

[29]

{29} J. Li and T. Jiang, "Efficient Inference of Haplotypes from Genotypes on a Pedigree," J. Bioinformatics and Computational Biology, vol. 1, pp. 41-69, 2003.

[30]

{30} M. Stephens, N. Smith, and P. Donnelly, "A New Statistical Method for Haplotype Reconstruction from Population Data," Am. J. Human Genetics, vol. 68, pp. 978-989, 2001.

[31]

{31} L. Eronen, F. Geerts, and H. Toivonen, "A Markov Chain Approach to Reconstruction of Long Haplotypes," Proc. Pacific Symp. Biocomputing, pp. 104-115, 2004.

Cited By

Negara SCodoban MDig DJohnson RJalote PBriand LHoek A(2014)Mining fine-grained code changes to detect unknown change patternsProceedings of the 36th International Conference on Software Engineering10.1145/2568225.2568317(803-813)Online publication date: 31-May-2014
https://dl.acm.org/doi/10.1145/2568225.2568317

Index Terms

TreeDT: Tree Pattern Mining for Gene Mapping

Recommendations

TreeDT: gene mapping by tree disequilibrium test
KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining

We introduce and evaluate TreeDT, a novel gene mapping method which is based on discovering and assessing tree-like patterns in genetic marker data. Gene mapping aims at discovering a statistical connection from a particular disease or trait to a narrow ...
A new semantic functional similarity over gene ontology

Identifying functionally similar or closely related genes and gene products has significant impacts on biological and clinical studies as well as drug discovery. In this paper, we propose an effective and practically useful method measuring both gene ...
Maximum Parsimony for Tree Mixtures

With the number of sequenced genomes growing ever larger, it is now common practice to concatenate sequence alignments from several genomic loci as a first step to phylogenetic tree inference. However, as different loci may support different trees due ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics

IEEE/ACM Transactions on Computational Biology and Bioinformatics Volume 3, Issue 2

April 2006

95 pages

ISSN:1545-5963

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 April 2006

Published in TCBB Volume 3, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
382
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)2

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Negara SCodoban MDig DJohnson RJalote PBriand LHoek A(2014)Mining fine-grained code changes to detect unknown change patternsProceedings of the 36th International Conference on Software Engineering10.1145/2568225.2568317(803-813)Online publication date: 31-May-2014
https://dl.acm.org/doi/10.1145/2568225.2568317

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents