Kaohsiung Journal of Medical Sciences
Volume 25, Issue 4 , Pages 165-176, April 2009

Dynamic Programming for Single Nucleotide Polymorphism ID Identification in Systematic Association Studies

  • Cheng-Hong Yang

      Affiliations

    • Department of Electronic Engineering, National Kaohsiung University of Applied Sciences;, Kaohsiung Medical University, Kaohsiung, Taiwan
    • ,
  • Li-Yeh Chuang

      Affiliations

    • Department of Chemical Engineering, I-Shou University;, Kaohsiung Medical University, Kaohsiung, Taiwan
    • ,
  • Yu-Huei Cheng

      Affiliations

    • Department of Electronic Engineering, National Kaohsiung University of Applied Sciences;, Kaohsiung Medical University, Kaohsiung, Taiwan
    • ,
  • Cheng-Hao Wen

      Affiliations

    • Faculty of Biomedical Science and Environmental Biology, Kaohsiung Medical University, Kaohsiung, Taiwan
    • ,
  • Hsueh-Wei Chang

      Affiliations

    • Faculty of Biomedical Science and Environmental Biology, Kaohsiung Medical University, Kaohsiung, Taiwan
    • Graduate Institute of Natural Products, College of Pharmacy, Kaohsiung Medical University, Kaohsiung, Taiwan
    • Center of Excellence for Environmental Medicine, Kaohsiung Medical University, Kaohsiung, Taiwan
    • Corresponding Author InformationAddress correspondence and reprint requests to: Dr Hsueh-Wei Chang, Department of Biomedical Science and Environmental Biology, Kaohsiung Medical University, 100 Shih-Chuan 1st Road, Kaohsiung 807, Taiwan

Received 26 December 2008; accepted 27 March 2009.

Article Outline

Single nucleotide polymorphisms (SNPs) play an important role in personalized medicine. However, the SNP data reported in many association studies provide only the SNP nucleotide/amino acid position, without providing the SNP ID recorded in National Center for Biotechnology Information databases. A tool with the ability to provide SNP ID identification, with a user-friendly interface, is needed. In this paper, a dynamic programming algorithm was used to compare homologs when the processed input sequence is aligned with the SNP FASTA database. Our novel system provides a web-based tool that uses the National Center for Biotechnology Information dbSNP database, which provides SNP sequence identification and SNP FASTA formats. Freely selectable sequence formats for alignment can be used, including general sequence formats (ACGT, [dNTP1/dNTP2] or IUPAC formats) and orientation with bidirectional sequence matching. In contrast to the National Center for Biotechnology Information SNP-BLAST, the proposed system always provides the correct targeted SNP ID (SNP hit), as well as nearby SNPs (flanking hits), arranged in their chromosomal order and contig positions. The system also solves problems inherent in SNP-BLAST, which cannot always provide the correct SNP ID for a given input sequence. Therefore, this system constitutes a novel application which uses dynamic programming to identify SNP IDs from the literature and keyed-in sequences for systematic association studies. It is freely available at http://bio.kuas.edu.tw/SNPosition/.

Key Words:  association studies , BLAST , BLAT , dynamic programming , single nucleotide polymorphisms

No full text is available. To read the body of this article, please view the PDF online.

 

Back to Article Outline

References 

  1. Suh Y , Vijg J . SNP discovery in associating genetic variation with human disease phenotypes . Mutat Res . 2005;573:41–53
  2. Erichsen HC , Chanock SJ . SNPs in cancer research and treatment . Br J Cancer . 2004;90:747–751
  3. Shastry BS . SNPs and haplotypes: genetic markers for disease and drug response (review) . Int J Mol Med . 2003;11:379–382
  4. Riva A , Kohane IS . SNPper: retrieval and analysis of human SNPs . Bioinformatics . 2002;18:1681–1685
  5. Kang HJ , Choi KO , Kim BD , et al.   FESD: a Functional Element SNPs Database in humans . Nucleic Acids Res . 2005;33:D518–D522
  6. Wang L , Liu S , Niu T , et al.   SNPHunter: a bioinformatic software for single nucleotide polymorphism data acquisition and management . BMC Bioinformatics . 2005;6:60
  7. Staats B , Qi L , Beerman M , et al.   Genewindow: an interactive tool for visualization of genomic variation . Nat Genet . 2005;37:109–110
  8. Savage D , Batley J , Erwin T , et al.   SNPServer: a realtime SNP discovery tool . Nucleic Acids Res . 2005;33:W493–W495
  9. University of Utah Genome Center  . GeneSNPs-blast function . Available at: http://www.genome.utah.edu/genesnps/cgi-bin/blast.cgi [Date accessed: August 23, 2006]
  10. McGinnis S , Madden TL . BLAST: at the core of a powerful and diverse set of sequence analysis tools . Nucleic Acids Res . 2004;32:W20–W25
  11. Sherry ST , Ward MH , Kholodov M , et al.   dbSNP: the NCBI database of genetic variation . Nucleic Acids Res . 2001;29:308–311
  12. National Center for Biotechnology Information  . SNP-BLAST . Available at: http://www.ncbi.nlm.nih.gov/SNP/snp_blastByOrg.cgi [Date accessed: January 9, 2009]
  13. Eddy SR . What is dynamic programming? . Nat Biotechnol . 2004;22:909–910
  14. Giegerich R . A systematic approach to dynamic programming in bioinformatics . Bioinformatics . 2000;16:665–677
  15. 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–453
  16. Altschul SF , Madden TL , Schaffer AA , et al.   Gapped BLAST and PSI-BLAST: a new generation of protein database search programs . Nucleic Acids Res . 1997;25:3389–3402
  17. Yang CH , Chuang LY , Cheng YH , et al.   SNP ID-info: SNP ID searching and visualization platform . OMICS . 2008;12:217–226
  18. Hinrichs AS , Karolchik D , Baertsch R , et al.   The UCSC Genome Browser Database: update 2006 . Nucleic Acids Res . 2006;34:D590–D598
  19. Kent WJ . BLAT—the BLAST-like alignment tool . Genome Res . 2002;12:656–664
  20. Zhang K , Qin Z , Chen T , et al.   HapBlock: haplotype block partitioning and tag SNP selection software using a set of dynamic programming algorithms . Bioinformatics . 2005;21:131–134
  21. Su SC , Kuo CC , Chen T . Inference of missing SNPs and information quantity measurements for haplotype blocks . Bioinformatics . 2005;21:2001–2007
  22. Chang HW , Yang CH , Chang PL , et al.   SNP-RFLPing: restriction enzyme mining for SNPs in genomes . BMC Genomics . 2006;7:30

PII: S1607-551X(09)70057-9

doi:10.1016/S1607-551X(09)70057-9

Kaohsiung Journal of Medical Sciences
Volume 25, Issue 4 , Pages 165-176, April 2009

Article Tools