Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci
BACKGROUND: Haplotype reconstruction is important in linkage mapping and association mapping of quantitative trait loci (QTL). One widely used statistical approach for haplotype reconstruction is simulated annealing (SA), implemented in SimWalk2. However, the algorithm needs a very large number of s...
Autores principales: | , , |
---|---|
Formato: | Texto |
Lenguaje: | English |
Publicado: |
BioMed Central
2008
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2375132/ https://www.ncbi.nlm.nih.gov/pubmed/18405361 http://dx.doi.org/10.1186/1471-2105-9-189 |
_version_ | 1782154584969445376 |
---|---|
author | Lee, Sang Hong Van der Werf, Julius HJ Kinghorn, Brian P |
author_facet | Lee, Sang Hong Van der Werf, Julius HJ Kinghorn, Brian P |
author_sort | Lee, Sang Hong |
collection | PubMed |
description | BACKGROUND: Haplotype reconstruction is important in linkage mapping and association mapping of quantitative trait loci (QTL). One widely used statistical approach for haplotype reconstruction is simulated annealing (SA), implemented in SimWalk2. However, the algorithm needs a very large number of sequential iterations, and it does not clearly show if convergence of the likelihood is obtained. RESULTS: An evolutionary algorithm (EA) is a good alternative whose convergence can be easily assessed during the process. It is feasible to use a powerful parallel-computing strategy with the EA, increasing the computational efficiency. It is shown that the EA can be ~4 times faster and gives more reliable estimates than SimWalk2 when using 4 processors. In addition, jointly updating dependent variables can increase the computational efficiency up to ~2 times. Overall, the proposed method with 4 processors increases the computational efficiency up to ~8 times compared to SimWalk2. The efficiency will increase more with a larger number of processors. CONCLUSION: The use of the evolutionary algorithm and the joint updating method can be a promising tool for haplotype reconstruction in linkage and association mapping of QTL. |
format | Text |
id | pubmed-2375132 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2008 |
publisher | BioMed Central |
record_format | MEDLINE/PubMed |
spelling | pubmed-23751322008-05-10 Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci Lee, Sang Hong Van der Werf, Julius HJ Kinghorn, Brian P BMC Bioinformatics Methodology Article BACKGROUND: Haplotype reconstruction is important in linkage mapping and association mapping of quantitative trait loci (QTL). One widely used statistical approach for haplotype reconstruction is simulated annealing (SA), implemented in SimWalk2. However, the algorithm needs a very large number of sequential iterations, and it does not clearly show if convergence of the likelihood is obtained. RESULTS: An evolutionary algorithm (EA) is a good alternative whose convergence can be easily assessed during the process. It is feasible to use a powerful parallel-computing strategy with the EA, increasing the computational efficiency. It is shown that the EA can be ~4 times faster and gives more reliable estimates than SimWalk2 when using 4 processors. In addition, jointly updating dependent variables can increase the computational efficiency up to ~2 times. Overall, the proposed method with 4 processors increases the computational efficiency up to ~8 times compared to SimWalk2. The efficiency will increase more with a larger number of processors. CONCLUSION: The use of the evolutionary algorithm and the joint updating method can be a promising tool for haplotype reconstruction in linkage and association mapping of QTL. BioMed Central 2008-04-11 /pmc/articles/PMC2375132/ /pubmed/18405361 http://dx.doi.org/10.1186/1471-2105-9-189 Text en Copyright © 2008 Lee et al; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an Open Access article distributed under the terms of the Creative Commons Attribution License ( (http://creativecommons.org/licenses/by/2.0) ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
spellingShingle | Methodology Article Lee, Sang Hong Van der Werf, Julius HJ Kinghorn, Brian P Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci |
title | Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci |
title_full | Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci |
title_fullStr | Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci |
title_full_unstemmed | Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci |
title_short | Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci |
title_sort | using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci |
topic | Methodology Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2375132/ https://www.ncbi.nlm.nih.gov/pubmed/18405361 http://dx.doi.org/10.1186/1471-2105-9-189 |
work_keys_str_mv | AT leesanghong usinganevolutionaryalgorithmandparallelcomputingforhaplotypinginageneralcomplexpedigreewithmultiplemarkerloci AT vanderwerfjuliushj usinganevolutionaryalgorithmandparallelcomputingforhaplotypinginageneralcomplexpedigreewithmultiplemarkerloci AT kinghornbrianp usinganevolutionaryalgorithmandparallelcomputingforhaplotypinginageneralcomplexpedigreewithmultiplemarkerloci |