Local alignment of two-base encoded DNA sequence

详细信息    查看全文

• 作者：Nils Homer (1) (2)
  Barry Merriman (2)
  Stanley F Nelson (2)
  
• 刊名：BMC Bioinformatics
• 出版年：2009
• 出版时间：December 2009
• 年：2009
• 卷：10
• 期：1
• 全文大小：266KB
• 参考文献：1. Hamming R: Error Detecting and Error Correcting Codes. / Bell System Technical Journal 1950, 29:147鈥?60.
  2. Levenshtein VI: Binary Codes Capable of Correcting Deletions, Insertions, and Reversals. / Soviet Physics Doklady 1966, 10:706鈥?10.
  3. Needleman SB, Wunsch CD: A general method applicable to the search for similarities in the amino acid sequence of two proteins. / J Mol Biol 1970, 48:443鈥?53. f="http://dx.doi.org/10.1016/0022-2836(70)90057-4">CrossRef
  4. Smith TF, Waterman MS: Identification of common molecular subsequences. / J Mol Biol 1981, 147:195鈥?97. f="http://dx.doi.org/10.1016/0022-2836(81)90087-5">CrossRef
  5. Gotoh O: An improved algorithm for matching biological sequences. / J Mol Biol 1982, 162:705鈥?08. f="http://dx.doi.org/10.1016/0022-2836(82)90398-9">CrossRef
  6. Hirschberg DS: A linear space algorithm for computing maximal common subsequences. / Commun ACM 1975, 18:341鈥?43. f="http://dx.doi.org/10.1145/360825.360861">CrossRef
  7. Huang X, Miller W: A time-efficient linear-space local similarity algorithm. / Adv Appl Math 1991, 12:337鈥?57. f="http://dx.doi.org/10.1016/0196-8858(91)90017-D">CrossRef
  8. Myers EW, Miller W: Optimal alignments in linear space. / Comput Appl Biosci 1988, 4:11鈥?7.
  9. Powell DR, Allison L, Dix TI: A versatile divide and conquer technique for optimal string alignment. / Inf Process Lett 1999, 70:127鈥?39. f="http://dx.doi.org/10.1016/S0020-0190(99)00053-8">CrossRef
  10. Ewans W, Grant G: Statistical Methods in Bioinformatics. New York: Springer 2002.
  11. Jones N, Pevzner P: An Introduction to Bioinformatics Algorithms (Computational Molecular Biology). Cambridge MA: The MIT Press 2004.
  12. Kent WJ: BLAT鈥搕he BLAST-like alignment tool. / Genome Res 2002, 12:656鈥?64.
  13. Rumble SM, Lacroute P, Dalca AV, Fiume M, Sidow A, Brudno M: SHRiMP: Accurate Mapping of Short Color-space Reads. / PLoS Comput Biol 2009, 5:e1000386. f="http://dx.doi.org/10.1371/journal.pcbi.1000386">CrossRef
  14. Li H, Ruan J, Durbin R: Mapping short DNA sequencing reads and calling variants using mapping quality scores. / Genome Res 2008, 18:1851鈥?858. f="http://dx.doi.org/10.1101/gr.078212.108">CrossRef
  15. Ma B, Tromp J, Li M: PatternHunter: faster and more sensitive homology search. / Bioinformatics 2002, 18:440鈥?45. f="http://dx.doi.org/10.1093/bioinformatics/18.3.440">CrossRef
  16. Applied Biosystems Incorporated: Principles of Di-Base Sequencing and the Advantages of Color Space Analysis in the SOLiD System. [f="http://marketing.appliedbiosystems.com/images/Product_Microsites/Solid_Knowledge_MS/pdf/SOLiD_Dibase_Sequencing_and_Color_Space_Analysis.pdf" class="a-plus-plus">http://marketing.appliedbiosystems.com/images/Product_Microsites/Solid_Knowledge_MS/pdf/SOLiD_Dibase_Sequencing_and_Color_Space_Analysis.pdf]
  17. Applied Biosystems Incorporated: A Theoretical Understanding of 2 Base Color Codes and Its Application to Annotation, Error Detection, and Error Correction. [f="http://www3.appliedbiosystems.com/cms/groups/mcb_marketing/documents/generaldocuments/cms_058265.pdf" class="a-plus-plus">http://www3.appliedbiosystems.com/cms/groups/mcb_marketing/documents/generaldocuments/cms_058265.pdf]
  18. Altschul SF, Madden TL, Schaffer AA, Zhang J, Zhang Z, Miller W, Lipman DJ: Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. / Nucleic Acids Res 1997, 25:3389鈥?402. f="http://dx.doi.org/10.1093/nar/25.17.3389">CrossRef
  19. Li R, Li Y, Kristiansen K, Wang J: SOAP: short oligonucleotide alignment program. / Bioinformatics 2008, 24:713鈥?14. f="http://dx.doi.org/10.1093/bioinformatics/btn025">CrossRef
  20. Ning Z, Cox AJ, Mullikin JC: SSAHA: a fast search method for large DNA databases. / Genome Res 2001, 11:1725鈥?729. f="http://dx.doi.org/10.1101/gr.194201">CrossRef
  21. Levy S, Sutton G, Ng PC, Feuk L, Halpern AL, Walenz BP, Axelrod N, Huang J, Kirkness EF, Denisov G, / et al.: The diploid genome sequence of an individual human. / PLoS Biol 2007, 5:e254. f="http://dx.doi.org/10.1371/journal.pbio.0050254">CrossRef
  22. Sherry ST, Ward MH, Kholodov M, Baker J, Phan L, Smigielski EM, Sirotkin K: dbSNP: the NCBI database of genetic variation. / Nucleic Acids Res 2001, 29:308鈥?11. f="http://dx.doi.org/10.1093/nar/29.1.308">CrossRef
  23. Ewing B, Green P: Base-calling of automated sequencer traces using phred. II. Error probabilities. / Genome Res 1998, 8:186鈥?94.
  24. Ewing B, Hillier L, Wendl MC, Green P: Base-calling of automated sequencer traces using phred. I. Accuracy assessment. / Genome Res 1998, 8:175鈥?85.
  25. Izmailov A, Goloubentzev D, Jin C, Sunay S, Wisco V, Yager TD: A general approach to the analysis of errors and failure modes in the base-calling function in automated fluorescent DNA sequencing. / Electrophoresis 2002, 23:2720鈥?728. f="http://dx.doi.org/10.1002/1522-2683(200208)23:16<2720::AID-ELPS2720>3.0.CO;2-Z">CrossRef
  26. Izmailov A, Yager TD, Zaleski H, Darash S: Improvement of base-calling in multilane automated DNA sequencing by use of electrophoretic calibration standards, data linearization, and trace alignment. / Electrophoresis 2001, 22:1906鈥?914. f="http://dx.doi.org/10.1002/1522-2683(200106)22:10<1906::AID-ELPS1906>3.0.CO;2-5">CrossRef
  27. Smith DR, Quinlan AR, Peckham HE, Makowsky K, Tao W, Woolf B, Shen L, Donahue WF, Tusneem N, Stromberg MP, / et al.: Rapid whole-genome mutational profiling using next-generation sequencing technologies. / Genome Res 2008, 18:1638鈥?642. f="http://dx.doi.org/10.1101/gr.077776.108">CrossRef
  
• 作者单位：Nils Homer (1) (2)
  Barry Merriman (2)
  Stanley F Nelson (2)
  
  1. Department of Computer Science, University of California Los Angeles, Los Angeles, California, 90095, USA
  2. Department of Human Genetics, David Geffen School of Medicine, University of California Los Angeles, Los Angeles, California, 90095, USA
  
• ISSN：1471-2105

文摘

Background DNA sequence comparison is based on optimal local alignment of two sequences using a similarity score. However, some new DNA sequencing technologies do not directly measure the base sequence, but rather an encoded form, such as the two-base encoding considered here. In order to compare such data to a reference sequence, the data must be decoded into sequence. The decoding is deterministic, but the possibility of measurement errors requires searching among all possible error modes and resulting alignments to achieve an optimal balance of fewer errors versus greater sequence similarity. Results We present an extension of the standard dynamic programming method for local alignment, which simultaneously decodes the data and performs the alignment, maximizing a similarity score based on a weighted combination of errors and edits, and allowing an affine gap penalty. We also present simulations that demonstrate the performance characteristics of our two base encoded alignment method and contrast those with standard DNA sequence alignment under the same conditions. Conclusion The new local alignment algorithm for two-base encoded data has substantial power to properly detect and correct measurement errors while identifying underlying sequence variants, and facilitating genome re-sequencing efforts based on this form of sequence data.