Optimal algorithms for haplotype assembly from whole-genome sequence data.
Optimal algorithms for haplotype assembly from whole-genome sequence data.
复制标题
DOI：
10.1093/bioinformatics/btq215
复制
发表时间：
2010-06-15
期刊：
影响因子：
--
通讯作者：
Eskin E
中科院分区：
文献类型：
--
作者：
He D;Choi A;Pipatsrisawat K;Darwiche A;Eskin E
动机：单倍型推断是人类基因组中遗传变异的许多类型分析的重要步骤。获得单倍型的传统方法涉及从个体群体中收集基因型信息，然后应用单倍型推理算法。高通量测序技术的发展允许通过组合序列片段来获得单倍型的替代策略。“单倍型组装”的问题是组装染色体的两个单倍型的问题，给定这样的片段或读段的集合及其在单倍型中的位置，其通过将读段映射到参考基因组来预先确定。读段中的错误显著增加了问题的难度，并且已经表明，即使对于长度为2的读段，该问题也是NP难的。现有的贪婪和随机算法不能保证找到单倍型组装问题的最优解。结果如下：在本文中，我们提出了一个动态规划算法，该算法能够以O（m × 2k × n）的时间复杂度最优地组装单倍型，其中m是读段数，k是最长读段的长度，n是单倍型中SNP的总数。我们还减少了单倍型组装问题的最大可满足性问题，往往可以解决最佳，即使当k是大的。利用我们的算法的效率，我们进行模拟实验，证明使用当前测序技术的典型长度的读段组装单体型是不切实际的。然而，我们证明了这种方法和传统的单倍型定相方法的组合，使我们能够实际构建包含常见和罕见变异的单倍型。联系人：danhe@cs.ucla.edu
Motivation: Haplotype inference is an important step for many types of analyses of genetic variation in the human genome. Traditional approaches for obtaining haplotypes involve collecting genotype information from a population of individuals and then applying a haplotype inference algorithm. The development of high-throughput sequencing technologies allows for an alternative strategy to obtain haplotypes by combining sequence fragments. The problem of ‘haplotype assembly’ is the problem of assembling the two haplotypes for a chromosome given the collection of such fragments, or reads, and their locations in the haplotypes, which are pre-determined by mapping the reads to a reference genome. Errors in reads significantly increase the difficulty of the problem and it has been shown that the problem is NP-hard even for reads of length 2. Existing greedy and stochastic algorithms are not guaranteed to find the optimal solutions for the haplotype assembly problem. Results: In this article, we proposed a dynamic programming algorithm that is able to assemble the haplotypes optimally with time complexity O(m × 2k × n), where m is the number of reads, k is the length of the longest read and n is the total number of SNPs in the haplotypes. We also reduce the haplotype assembly problem into the maximum satisfiability problem that can often be solved optimally even when k is large. Taking advantage of the efficiency of our algorithm, we perform simulation experiments demonstrating that the assembly of haplotypes using reads of length typical of the current sequencing technologies is not practical. However, we demonstrate that the combination of this approach and the traditional haplotype phasing approaches allow us to practically construct haplotypes containing both common and rare variants. Contact: danhe@cs.ucla.edu
登录
查看更多内容
影响因子：
30.8
作者：
Marchini, Jonathan;Howie, Bryan;Donnelly, Peter
通讯作者：
Donnelly, Peter
影响因子：
64.8
作者：
Frazer, Kelly A.;Ballinger, Dennis G.;Cox, David R.;Hinds, David A.;Stuve, Laura L.;Gibbs, Richard A.;Belmont, John W.;Boudreau, Andrew;Hardenbol, Paul;Leal, Suzanne M.;Pasternak, Shiran;Wheeler, David A.;Willis, Thomas D.;Yu, Fuli;Yang, Huanming;Zeng, Changqing;Gao, Yang;Hu, Haoran;Hu, Weitao;Li, Chaohua;Lin, Wei;Liu, Siqi;Pan, Hao;Tang, Xiaoli;Wang, Jian;Wang, Wei;Yu, Jun;Zhang, Bo;Zhang, Qingrun;Zhao, Hongbin;Zhao, Hui;Zhou, Jun;Gabriel, Stacey B.;Barry, Rachel;Blumenstiel, Brendan;Camargo, Amy;Defelice, Matthew;Faggart, Maura;Goyette, Mary;Gupta, Supriya;Moore, Jamie;Nguyen, Huy;Onofrio, Robert C.;Parkin, Melissa;Roy, Jessica;Stahl, Erich;Winchester, Ellen;Ziaugra, Liuda;Altshuler, David;Shen, Yan;Yao, Zhijian;Huang, Wei;Chu, Xun;He, Yungang;Jin, Li;Liu, Yangfan;Shen, Yayun;Sun, Weiwei;Wang, Haifeng;Wang, Yi;Wang, Ying;Xiong, Xiaoyan;Xu, Liang;Waye, Mary M. Y.;Tsui, Stephen K. W.;Wong, J. Tze-Fei;Galver, Luana M.;Fan, Jian-Bing;Gunderson, Kevin;Murray, Sarah S.;Oliphant, Arnold R.;Chee, Mark S.;Montpetit, Alexandre;Chagnon, Fanny;Ferretti, Vincent;Leboeuf, Martin;Olivier, Jean-Franccois;Phillips, Michael S.;Roumy, Stephanie;Sallee, Clementine;Verner, Andrei;Hudson, Thomas J.;Kwok, Pui-Yan;Cai, Dongmei;Koboldt, Daniel C.;Miller, Raymond D.;Pawlikowska, Ludmila;Taillon-Miller, Patricia;Xiao, Ming;Tsui, Lap-Chee;Mak, William;Song, You Qiang;Tam, Paul K. H.;Nakamura, Yusuke;Kawaguchi, Takahisa;Kitamoto, Takuya;Morizono, Takashi;Nagashima, Atsushi;Ohnishi, Yozo;Sekine, Akihiro;Tanaka, Toshihiro;Tsunoda, Tatsuhiko;Deloukas, Panos;Bird, Christine P.;Delgado, Marcos;Dermitzakis, Emmanouil T.;Gwilliam, Rhian;Hunt, Sarah;Morrison, Jonathan;Powell, Don;Stranger, Barbara E.;Whittaker, Pamela;Bentley, David R.;Daly, Mark J.;de Bakker, Paul I. W.;Barrett, Jeff;Chretien, Yves R.;Maller, Julian;McCarroll, Steve;Patterson, Nick;Pe'er, Itsik;Price, Alkes;Purcell, Shaun;Richter, Daniel J.;Sabeti, Pardis;Saxena, Richa;Schaffner, Stephen F.;Sham, Pak C.;Varilly, Patrick;Altshuler, David;Stein, Lincoln D.;Krishnan, Lalitha;Smith, Albert Vernon;Tello-Ruiz, Marcela K.;Thorisson, Gudmundur A.;Chakravarti, Aravinda;Chen, Peter E.;Cutler, David J.;Kashuk, Carl S.;Lin, Shin;Abecasis, Goncalo R.;Guan, Weihua;Li, Yun;Munro, Heather M.;Qin, Zhaohui Steve;Thomas, Daryl J.;McVean, Gilean;Auton, Adam;Bottolo, Leonardo;Cardin, Niall;Eyheramendy, Susana;Freeman, Colin;Marchini, Jonathan;Myers, Simon;Spencer, Chris;Stephens, Matthew;Donnelly, Peter;Cardon, Lon R.;Clarke, Geraldine;Evans, David M.;Morris, Andrew P.;Weir, Bruce S.;Tsunoda, Tatsuhiko;Johnson, Todd A.;Mullikin, James C.;Sherry, Stephen T.;Feolo, Michael;Skol, Andrew
通讯作者：
Skol, Andrew
影响因子：
5.8
作者：
Halperin, E;Eskin, E
通讯作者：
Eskin, E
DOI：
10.3233/978-1-58603-929-5-613
发表时间：
2009-01-01
期刊：
HANDBOOK OF SATISFIABILITY
影响因子：
--
作者：
Li, Chu Min;Manya, Felip
通讯作者：
Manya, Felip
影响因子：
7
作者：
Li, Heng;Ruan, Jue;Durbin, Richard
通讯作者：
Durbin, Richard