Efficient algorithms for the discovery of DNA oligonucleotide barcodes from sequence databases
- 21 April 2009
- journal article
- Published by Wiley in Molecular Ecology Resources
- Vol. 9 (s1) , 58-64
Abstract
Efficient design of barcode oligonucleotides can lead to significant cost reductions in the manufacturing of DNA arrays. Previous methods are based on either a preliminary alignment, which reduces their efficiency for intron‐rich regions, or on a brute force approach, not feasible for large‐scale problems or on data structures with very poor performance in the worst case. One of the algorithms we propose uses ‘oligonucleotide sorting’ for the discovery of oligonucleotide barcodes of given sizes, with good asymptotic performance. Specific barcode oligonucleotides with at least one base difference from other sequences in a database are found for each individual sequence. With another algorithm, specific oligonucleotides can also be found for groups or clades in the database, which have 100% homology for all oligonucleotide sequences within the group or clade while having differences with the rest of the data. By re‐organizing the sequences/groups in the database, oligonucleotides for different hierarchical levels can be found. The oligonucleotides or polymorphism locations identified as species or clade specific by the new algorithm are refined and screened further for hybridization thermodynamic properties with third party software.Keywords
This publication has 30 references indexed in Scilit:
- A high density COX1 barcode oligonucleotide array for identification and detection of species of Penicillium subgenus PenicilliumMolecular Ecology Resources, 2009
- Microarrays for Rapid Identification of Plant VirusesAnnual Review of Phytopathology, 2007
- Macroarray Detection of Plant RNA Viruses Using Randomly Primed and Amplified Complementary DNAs from Infected PlantsPhytopathology®, 2007
- Molecular diagnostics of soilborne fungal pathogens.2007
- Recent Developments in Pathogen Detection Arrays: Implications for Fungal Plant Pathogens and Use in PracticePhytopathology®, 2005
- PROBEmer: a web-based software tool for selecting optimal DNA oligosNucleic Acids Research, 2003
- An Oligonucleotide Array for the Identification and Differentiation of Bacteria Pathogenic on PotatoPhytopathology®, 2003
- DNA Microarray Technology: Devices, Systems, and ApplicationsAnnual Review of Biomedical Engineering, 2002
- Reducing the space requirement of suffix treesSoftware: Practice and Experience, 1999
- Identification of Some Oomycetes by Reverse Dot Blot HybridizationPhytopathology®, 1998