A random-permutations-based approach to fast read alignment
作者： Roy Lederman
DOI: 10.1186/1471-2105-14-S5-S8
关键词:
摘要: Read alignment is a computational bottleneck in some sequencing projects. Most of the existing software packages for read are based on two algorithmic approaches: prefix-trees and hash-tables. We propose new approach to using random permutations strings. present prototype implementation experiments performed with simulated real reads human DNA. Our indicate that this permutations-based several times faster than comparable programs fast it aligns more correctly. This may lead improved speed, sensitivity, accuracy alignment. The algorithm can also be used specialized applications extended other related problems, such as assembly. More information: http://alignment.commons.yale.edu
biomedcentral.com
springer.com
paperity.org参考文章(17)
Faraz Hach, Fereydoun Hormozdiari, Can Alkan, Farhad Hormozdiari, Inanc Birol, Evan E Eichler, S Cenk Sahinalp, mrsFAST: a cache-oblivious algorithm for short-read mapping Nature Methods. ,vol. 7, pp. 576- 577 ,(2010) , 10.1038/NMETH0810-576
Moses S. Charikar, Similarity estimation techniques from rounding algorithms symposium on the theory of computing. pp. 380- 388 ,(2002) , 10.1145/509907.509965
Paul Flicek, Ewan Birney, Sense from sequence reads: methods for alignment and assembly Nature Methods. ,vol. 6, pp. 479- ,(2009) , 10.1038/NMETH.1376
Vladimir Rokhlin, Andrei Osipov, Peter Wilcox Jones, A Randomized Approximate Nearest Neighbors Algorithm ,(2012)
H. Li, N. Homer, A survey of sequence alignment algorithms for next-generation sequencing. Briefings in Bioinformatics. ,vol. 11, pp. 473- 483 ,(2010) , 10.1093/BIB/BBQ015
Ruiqiang Li, Chang Yu, Yingrui Li, Tak-Wah Lam, Siu-Ming Yiu, Karsten Kristiansen, Jun Wang, None, SOAP2: an improved ultrafast tool for short read alignment. Bioinformatics. ,vol. 25, pp. 1966- 1967 ,(2009) , 10.1093/BIOINFORMATICS/BTP336
H. Li, R. Durbin, Fast and accurate short read alignment with Burrows–Wheeler transform Bioinformatics. ,vol. 25, pp. 1754- 1760 ,(2009) , 10.1093/BIOINFORMATICS/BTP324
Athena Ahmadi, Alexander Behm, Nagesh Honnalli, Chen Li, Lingjie Weng, Xiaohui Xie, Hobbes: optimized gram-based methods for efficient read alignment Nucleic Acids Research. ,vol. 40, ,(2012) , 10.1093/NAR/GKR1246
Ben Langmead, Cole Trapnell, Mihai Pop, Steven L Salzberg, Ultrafast and memory-efficient alignment of short DNA sequences to the human genome Genome Biology. ,vol. 10, pp. 1- 10 ,(2009) , 10.1186/GB-2009-10-3-R25
Richard M Durbin, David L Altshuler, Gonçalo R Abecasis, David R Bentley, Aravinda Chakravarti, Andrew G Clark, Francis S Collins, M Francisco, Peter Donnelly, Michael Egholm, Paul Flicek, Stacey B Gabriel, Richard A Gibbs, Bartha M Knoppers, Eric S Lander, Hans Lehrach, Elaine R Mardis, Gil A McVean, Debbie A Nickerson, Leena Peltonen, Alan J Schafer, Stephen T Sherry, Jun Wang, Richard K Wilson, David Deiros, Mike Metzker, Donna Muzny, Jeff Reid, David Wheeler, Jingxiang Li, Min Jian, Guoqing Li, Ruiqiang Li, Huiqing Liang, Geng Tian, Bo Wang, Jian Wang, Wei Wang, Huanming Yang, Xiuqing Zhang, Huisong Zheng, Lauren Ambrogio, Toby Bloom, Kristian Cibulskis, Tim J Fennell, David B Jaffe, Erica Shefler, Carrie L Sougnez, Niall Gormley, Sean Humphray, Zoya Kingsbury, Paula Koko-Gonzales, Jennifer Stone, Kevin J McKernan, Gina L Costa, Jeffry K Ichikawa, Clarence C Lee, Ralf Sudbrak, Tatiana A Borodina, Andreas Dahl, Alexey N Davydov, Peter Marquardt, Florian Mertes, Wilfiried Nietfeld, Philip Rosenstiel, Stefan Schreiber, Aleksey V Soldatov, Bernd Timmermann, Marius Tolzmann, Jason Affourtit, Dana Ashworth, Said Attiya, Melissa Bachorski, Eli Buglione, Adam Burke, Amanda Caprio, Christopher Celone, Shauna Clark, David Conners, Brian Desany, Lisa Gu, Lorri Guccione, Kalvin Kao, Andrew Kebbel, Jennifer Knowlton, Matthew Labrecque, Louise McDade, Craig Mealmaker, Melissa Minderman, Anne Nawrocki, Faheem Niazi, Kristen Pareja, Ravi Ramenani, David Riches, Wanmin Song, Cynthia Turcotte, Shally Wang, David Dooling, Lucinda Fulton, Robert Fulton, George Weinstock, John Burton, David M Carter, Carol Churcher, Alison Coffey, Anthony Cox, Aarno Palotie, Michael Quail, Tom Skelly, James Stalker, Harold P Swerdlow, Daniel Turner, Anniek De Witte, Shane Giles, Matthew Bainbridge, Danny Challis, Aniko Sabo, Fuli Yu, Jin Yu, Xiaodong Fang, Xiaosen Guo, Yingrui Li, Ruibang Luo, Shuaishuai Tai, Honglong Wu, Hancheng Zheng, Xiaole Zheng, Yan Zhou, Gabor T Marth, Erik P Garrison, Weichun Huang, Amit Indap, Deniz Kural, Wan-Ping Lee, Wen Fung Leong, Aaron R Quinlan, Chip Stewart, Michael P Stromberg, Alistair N Ward, Jiantao Wu, Charles Lee, Ryan E Mills, Xinghua Shi, Mark J Daly, Mark A DePristo, Aaron D Ball, Eric Banks, Brian L Browning, Kiran V Garimella, Sharon R Grossman, None, A map of human genome variation from population-scale sequencing PMC. ,(2010)