10.6 Integration of BLAST into NeoCore XMS

   

---

Sequence alignment tools are fundamental in the bioinformatics arena. A sequence alignment tool compares two or more sequences in order to determine how similar the sequences are or if subsections of the sequences are similar. A common use of the tool is for a researcher who sequences a section of DNA to then access a database and search for other DNA sequences that are similar to the one being studied. Finding other sequences in the database that are similar is a first step in trying to determine the functionality of the gene or to determine other organisms that may have a similar gene. Comparisons do not have to be comparing nucleotide sequence against nucleotide sequence or amino acid sequence against amino acid sequence. Since we know that nucleotide sequences code for amino acid sequences, we can convert nucleotide sequences to their equivalent amino acid sequence and compare sequences on those terms. This is often done because proteins are the functional element in life, and functional information is typically being sought.

Needleman-Wunsch are credited with coming up with the first global sequence alignment algorithm in 1970 (Needleman and Wunsch 1970). A global alignment compares the sequences over the entire length of both sequences. Gaps are added to force the two sequences to be the same length. Dynamic programming, a well-known optimization technique, is used to find the alignment(s) that produce the highest score. A more computationally efficient version was found by Gotoh in 1982.

Smith and Waterman generalized the Needleman-Wunsch algorithm in 1981 to find the highest-scoring subsequence matches between two sequences (Smith and Waterman 1981). Their method includes gap analysis and also uses a dynamic programming approach to find the best matches. The Smith-Waterman algorithm is still in popular use today.

The main problem with the Smith-Waterman sequence alignment algorithm is that it is computationally expensive and therefore very time consuming when comparing a given sequence against a large database of sequences. To improve search speed, a number of heuristic sequence alignment methods have been developed, such as those used in BLAST, FASTA, and SALSA. Of these heuristic methods, BLAST (Basic Local Alignment Search Tool) seems to be the most popular and well known (Altschul et al. 1990; Altschul et al. 1997). The heuristic algorithms are not guaranteed to find optimal alignment solutions, but they are far more practical for searching a large database of sequences, and they do a very good job of finding similar sequences.

It is beyond the scope of this chapter to go into the details of the various search algorithms. Numerous books are available that do cover these details, including (Durbin et al. 1998).

NeoCore developed its own sequence search plug-in module to go with NeoCore XMS. The NeoCore sequence search plug-in is similar to BLAST in operation but is based on NeoCore's patented digital pattern processing technology. The plug-in gives the power of a BLAST sequence search embedded (SSE) within a query of the XML database, which has the added advantage of being able to do targeted BLAST searches. In addition to looking for sequences that are similar to a query sequence, the query can restrict the search to DNA sequences from a particular organism or sequences involved in a particular metabolic pathway. Any set of sequences that can be targeted with an XPath query can have a BLAST search performed on it.

The NeoCore SSE plug-in is accessed via a function call within an XPath query. An example XPath query that calls the SSE is

/ND/dna_sequence_entry/dna_sequence{func("Blastn,-w11,-r1,-q3, -i actgcggt . . . ")}/..

This query searches all DNA sequence entries within NeoCore XMS, targeted by /ND/dna_sequence_entry/dna_sequence. NeoCore XMS wraps all documents within the tags <ND>, hence the /ND at the beginning of the XPath query. The query returns all nucleotide sequences that are similar to the query sequence actgcggt . . .. Similarity is based on the BLAST scoring algorithm. The addition to the standard XPath query is the function call section starting and ending with curly brackets, { func("Blastn, . . . ")}. Five separate function calls and a variety of parameters are supported by the NeoCore SSE. The five functions mimic those of BLAST and for convenience are named the same as BLAST calls.

10.6.1 Sequence Search Types

This section describes the various sequence search types supported by NeoCore SSE. The five functions supported are

• Protein-Protein Search (Blastp)

  This search compares an amino acid query sequence against amino acid sequences stored in the database.

• Nucleotide-Nucleotide Search (Blastn)

  This search compares a nucleotide query sequence against nucleotide sequences stored in the database.

• Nucleotide-Protein Search (Blastx)

  This search compares a nucleotide query sequence against amino acid sequences stored in the database. The nucleotide query sequence is first translated into a set of six possible amino acid sequences. The six amino acid sequences come from the six possible reading frames of the nucleotide sequence.

• Protein-Nucleotide Search (tBlastn)

  This search compares an amino acid query sequence against nucleotide sequences stored in the database. The nucleotide sequences in the database are dynamically translated in all six reading frames during the sequence search to their equivalent amino acid sequences and then compared to the protein sequence.

• Translated Nucleotide-Nucleotide Search (tBlastx)

  This search compares a nucleotide query sequence, translated into six possible amino acid sequences, against nucleotide sequences stored in the database. The nucleotide sequences in the database are dynamically translated in all six reading frames during the sequence search and then compared to the six translated protein sequences.

Determining the set of nucleotides that make up a DNA sequence is but one step in the discovery process. The question arises as to how one goes about finding a gene, or a section of the DNA sequence that codes for a protein. It is not at all obvious from sequencing one side of a DNA strand where the genes lie. Similarity searches play a role in this process of discovering genes. If the sequence information that comes from one side of a DNA strand is translated into its various possible amino acid sequences via the genetic code table, a database of proteins can be searched looking for possible matches. If matches are found, then the corresponding section of the DNA may be a gene.

If the human genome may be thought of as the book of life that contains the blueprints for our construction, a mechanism must exist to indicate starting and stopping points. During protein construction within the cell, as genes are read, certain amino acids act as initiators and others act as terminators. The amino acid Methionine is the initiator or starting point for a gene and is coded for by the DNA sequence A-T-G in the genetic code table. As with any construction process, instructions for the ending or completion of the project must exist. Three stop codons serve this purpose. The DNA sequences T-A-A, T-G-A, or T-A-G do not code for an amino acid but act as signals to complete the protein under construction. The newly constructed protein begins with Methionine and ends just before one of the stop codons. Regions bounded by start and stop codons are known as Open Reading Frames (ORF). An ORF represents a possible gene-coding region in the nucleotide sequence. A DNA sequence may have six potential overlapping reading frames that must be evaluated.

As previously mentioned, DNA is a double-stranded molecule. Genes may be found on either the forward or reverse strand. The forward and reverse strands are related because of the pairing of the nucleotides across from one another. A Cytosine will pair only with a Guanine, and a Thymine will pair only with an Adenine.

Forward strand 
C A T G C A T G C A T C
G T A C G T A C G T A G
Reverse strand 

In translating the forward sequence, the first three frames are found (remember that it takes three nucleotides to code for one amino acid, and we are not sure where the starting point is):

Frame 2:	C	ATG	CAT	GCA	TC	Begin translating at the second nucleotide
		M	H	A	S

Frame 3:	CA	TGC	ATG	CAT	C	Begin translating at the third nucleotide
		C	M	H

To translate the reverse frames for evaluation the strand becomes:

G A T G C A T G C A T G

Frame 4:	GAT	GCA	TGC	ATG	Begin translation with the first nucleotide
	D	A	C	M

Frame 5:	G	ATG	CAT	GCA	TG	Begin translation with the second nucleotide
		M	H	A

Frame 6:	GA	TGC	ATG	CAT	G	Begin translation with the third nucleotide
		C	M	H

Frames 2 and 5 begin with the Methionine initiator (M) or start signal. If one of these two strands ends with one of the stop codons, this would tend to indicate a gene-coding region that results in a manufactured protein. Another point that arises from this example is illustrated in Frame 2. Only two nucleotides are known at the end. No matter what the third nucleotide is, this codon will translate to amino acid S or serine. As previously mentioned, the genetic code contains redundancies in coding. Serine may be coded for by any of the following codons: TCA, TCG, TCT, TCC, AGT, and AGC. Methionine, the initiator of the protein chain, is coded for by the unique codon ATG. Except for BLASTp and BLASTn, examining the six reading frames is at the core of performing comprehensive BLAST searches. This search capability is an example of the ability to include powerful plug-ins within NeoCore XMS.

A couple of examples will demonstrate the use of the BLAST search engine with NeoCore XMS. NeoCore XMS was loaded with several bacterial genomes downloaded from NCBI. The XML format of the sequence entries can be assumed to be that shown in earlier sections of this chapter. The first example is a BLASTp. BLASTp compares an amino acid query sequence against amino acid sequences in the database. The XPath query is of the form shown in Listing 10.4.

Listing 10.4 XPath Query

/ND/dna_sequence_entry/features/gene/protein/amino_acid_sequence
{func("Blastn, -i  . . . KFGGTSVANAERFLRVADILESNARQGQVA . . . ")}/..

This query searches for all proteins similar to the query sequence ". . . KFGGTSVANA . . ." and targeted by XPath:

/ND/dna_sequence_entry/features/gene/protein/amino_acid_sequence

The trailing / . . . will cause the return XML to be at the <protein> element level. The return from this query will be of the form shown in Listing 10.5.

Listing 10.5 Result of the Query in Listing 10.4

<query_results>
      <protein>
            <gene>aspartokinase II</gene>
            <protein_id>AAC76922.1</protein_id>
            <db_xref>GI:1790376</db_xref>
            <amino_acid_sequence>
                  ...KFGGSSLADVKCYLRVAGIMAEYSQPDDMMVVSAA...
            <amino_acid_sequence>
      </protein>
</query_results>

NeoCore XMS always returns well-formed XML. To view details on the sequence matches, there is an option to output a file of search results. One of the results output from this search is shown in Listing 10.6.

Listing 10.6 File Containing Search Results for Listing 10.5

protein_id: AAC76922.1
DB Seq. Offset:   15
QuerySeq. Offset:  4
SA Length:        35
SA Score:         61
DB Sequence:      KFGGSSLADVKCYLRVAGIMAEYSQPDDMMVVSAA
Query Sequence:   KFGGTSVANAERFLRVADILESNARQGQVATVLSA

In this case a subsequence of 35 amino acids from query sequence starting at offset 4 from the beginning of the query sequence, matched a subsequence from the database, starting at offset 15, with a score of 61. The score is built by adding up alignment scores for each pair of amino acids over the subsequence at hand. Exact matches give the highest score. Over the set of 20 amino acids, there are amino acids that have similar properties to one another. Alignments with amino acids that have similar properties will still add to the score in a positive way. Alignments with amino acids that have dissimilar properties will cause a negative penalty to be added to the score. Sequence substitution matrices provide alignment scores for all possible combinations of two amino acids. It is beyond the scope of this chapter to go into how the sequence substitution matrix scoring is generated. The first couple of chapters in Durbin et al. 1998 provide a very readable development of sequence alignment methodologies and the generation of scoring matrices.

A more complex BLAST search can be performed using the tBLASTx option. The query format is shown in Listing 10.7.

Listing 10.7 A Complex Query Using the tBLASTx Option

/ND/dna_sequence_entry[source/taxonomy/cell_type="Eukaryota"]/dna_
sequence {func("tBlastx, -i 
gtaccctgtttacatcattttgccattttcgcgtactgcaaccggcggg . . . 
")}/../header/accession_no

This query performs a tBLASTx search against all DNA sequences in that database that come from a taxonomy cell type of Eukaryota. The query will return the accession number of all database sequences that meet the tBLASTx criteria. A typical result will look like Listing 10.8.

Listing 10.8 Result of the Query in Listing 10.7

<query_results>
      <accession_no>
            <base_no>AE000333</base_no>
            <version>AE000333.1</version>
            <GI>GI:1788805</GI>
      </accession_no>
</query_results>

A tBLASTx search first converts the query sequence into the six amino acid frames. The sequence search engine then compares the six query frames to each database sequence that is of the cell type Eukaryota. Before the comparison can be done, the database DNA sequences must first be dynamically converted to its six amino acid frames. The comparison is then performed at the amino acid sequence level. Using NeoCore's DPP technology, all six query sequences are compared to each database sequence in a single pass over the database sequences. The result is a very fast and accurate search. An example of one of the database matches is given in Listing 10.9.

Listing 10.9 Example Database Match for Amino Acid Sequence Comparison

Accession_no: AE000140.1
DB Seq Frame No:  2
Query Frame No:   6
DB Seq. Offset:   2728
QuerySeq. Offset: 592
SA Length:        32
SA Score:         53
DB Sequence:      FRVVAPSTHRRAGTGGVAGIQRNLLHSLHFRH
Query Sequence:   FRLVTQSEQGRAGAGDTARYRADFLRAMHHQQ

Notice how query sequence frame number 6 matched with a database sequence frame number 2. Since the query sequence match was on the reverse frame 6, the query sequence offset, 592, would be referenced from the tail end of the query nucleotide sequence. The database sequence matched on a forward frame 2, so the offset is from the beginning of the database nucleotide sequence. Nucleotide sequences tend to be much longer than amino acid sequences (at least by a factor of 3), hence the large offset numbers. The match subsequence is shown in the amino acid domain. The score is generated in the same fashion as a BLASTp type of search.

Sequence search and alignment tools are the heart and soul of data-mining in the high throughput genomics world. These are primary tools for the biologist today. The incorporation of a BLAST search engine into NeoCore XMS greatly enhances the database's ability to meet the information requirements of the exploding life sciences market.

---

Top Title TOC Preface P.1 What Is XML? P.2 XML Concepts P.3 XML-Related Technologies P.4 XML Data Management P.5 How This Book Is Organized P.6 Who Should Read This Book P.7 Resources Acknowledgments Chapter 8 Chapter 12 Chapter 13 Chapter 14 Chapter 19 Part I: What Is XML? Chapter 1. Information Modeling with XML 1.1 Introduction 1.2 XML as an Information Domain 1.3 How XML Expresses Information 1.4 Patterns in XML 1.5 Common XML Information-Modeling Pitfalls 1.6 A Very Simple Way to Design XML 1.7 Conclusion Part II: Native XML Databases Chapter 2. Tamino-Software AG's Native XML Server 2.1 Introduction 2.2 Tamino Architecture and APIs 2.3 XML Storage 2.4 Querying XML 2.5 Tools 2.6 Full Database Functionality 2.7 Conclusion Chapter 3. eXist Native XML Database 3.1 Introduction 3.2 Features 3.3 System Architecture Overview 3.4 Getting Started 3.5 Query Language Extensions 3.6 Application Development 3.7 Technical Background 3.8 Conclusion Chapter 4. Embedded XML Databases 4.1 Introduction 4.2 A Primer on Embedded Databases 4.3 Embedded XML Databases 4.4 Building Applications for Embedded XML Databases 4.5 Conclusion Part III: XML and Relational Databases Chapter 5. IBM XML-Enabled Data Management Product Architecture & Technology 5.1 Introduction 5.2 Product and Technology Offering Summaries 5.3 Current Architecture and Technology 5.4 Future Architecture and Technology 5.5 Conclusion Notices Chapter 6. Supporting XML in Oracle9i 6.1 Introduction 6.2 Storing XML as CLOB 6.3 XMLType 6.4 Using XSU for Fine-Grained Storage 6.5 Building XML Documents from Relational Data 6.6 Web Access to the Database 6.7 Special Oracle Features 6.8 Conclusion Chapter 7. XML Support in Microsoft SQL Server 2000 7.1 Introduction 7.2 XML and Relational Data 7.3 XML Access to SQL Server 7.4 Serializing SQL Query Results into XML 7.5 Providing Relational Views over XML 7.6 SQLXML Templates 7.7 Providing XML Views over Relational Data 7.8 Conclusion Chapter 8. A Generic Architecture for Storing XML Documents in a Relational Database 8.1 Introduction 8.2 System Architecture 8.3 The Data Model 8.4 Creating the Database 8.5 Connecting to the Repository 8.6 Uploading XML Documents 8.7 Querying the Repository 8.8 Further Enhancements 8.9 Conclusion Chapter 9. An Object-Relational Approach to Building a High-Performance XML Repository 9.1 Introduction 9.2 Overview of XML Use-Case Scenario 9.3 High-Level System Architecture 9.4 Detailed Design Descriptions 9.5 Conclusion Part IV: Applications of XML Chapter 10. Knowledge Management in Bioinformatics 10.1 Introduction 10.2 A Brief Molecular Biology Background 10.3 Life Sciences Are Turning to XML to Model Their Information 10.4 A Genetic Information Model 10.5 NeoCore XMS* 10.6 Integration of BLAST into NeoCore XMS Conclusion Chapter 11. Case Studies of XML Used with IBM DB2 Universal Database 11.1 Introduction 11.2 Case Study 1: "Our Most Valued Customers Come First" 11.3 Case Study 2: "Improve Cash Flow" 11.4 Conclusion Notices Chapter 12. The Design and Implementation of an Engineering Data Management System Using XML and J2EE 12.1 Introduction 12.2 Background and Requirements 12.3 Overview 12.4 Design Choices 12.5 Future Directions 12.6 Conclusion Chapter 13. Geographical Data Interchange Using XML-Enabled Technology within the GIDB System 13.1 Introduction 13.2 GIDB METOC Data Integration 13.3 GIDB Web Map Service Implementation 13.4 GIDB GML Import and Export 13.5 Conclusion Chapter 14. Space Wide Web by Adapters in Distributed Systems Configuration from Reusable Components 14.1 Introduction 14.2 Advanced Concept Description: The Research Problem 14.3 Integration of Components with Architecture 14.4 Example 14.5 Future Generation NASA Institute for Advanced Concepts, Space Wide Web Research, and Boundaries 14.6 Advanced Concept Development 14.7 Conclusion Chapter 15. XML as a Unifying Framework for Inductive Databases 15.1 Introduction 15.2 Past Work 15.3 The Proposed Data Model: XDM 15.4 Benefits of XDM 15.5 Toward Flexible and Open Systems 15.6 Related Work 15.7 Conclusion Chapter 16. Designing and Managing an XML Warehouse 16.1 Introduction 16.2 Architecture 16.3 Data Warehouse Specification 16.4 Managing the Metadata 16.5 Storage and Management of the Data Warehouse 16.6 DAWAX: A Graphic Tool for the Specification and Management of a Data Warehouse 16.7 Related Work 16.8 Conclusion Part V: Performance and Benchmarks Chapter 17. XML Management System Benchmarks 17.1 Introduction 17.2 Benchmark Specification 17.3 Benchmark Data Set 17.4 Existing Benchmarks for XML 17.5 Conclusion Chapter 18. The Michigan Benchmark: A Micro-Benchmark for XML Query Performance Diagnostics 18.1 Introduction 18.2 Related Work 18.3 Benchmark Data Set 18.4 Benchmark Queries 18.5 Using the Benchmark 18.6 Conclusion Chapter 19. A Comparison of Database Approaches for Storing XML Documents 19.1 Introduction 19.2 Data Models for XML Documents 19.3 Databases for Storing XML Documents 19.4 Benchmarking Specification 19.5 Test Results 19.6 Related Work 19.7 Summary Chapter 20. Performance Analysis between an XML-Enabled Database and a Native XML Database 20.1 Introduction 20.2 Related Work 20.3 Methodology 20.4 Database Design 20.5 Discussion 20.6 Experiment Result 20.7 Conclusion Chapter 21. Conclusion References Contributors Editors Chapter 1: Information Modeling with XML Chapter 2: Tamino-Software AG's Native XML Server Chapter 3: eXist Native XML Database Chapter 4: Embedded XML Databases Chapter 5: IBM XML-Enabled Data Management Product Architecture and Technology Chapter 6: Supporting XML in Oracle9i Chapter 7: XML Support in Microsoft SQL Server 2000 Chapter 8: A Generic Architecture for Storing XML Documents in a Relational Database Chapter 9: An Object-Relational Approach to Building a High-Performance XML Repository Chapter 10: Knowledge Management in Bioinformatics Chapter 11: Case Studies of XML Used with IBM DB2 Universal Database Chapter 12: The Design and Implementation of an Engineering Data Management System Using XML and J2EE Chapter 13: Geographical Data Interchange Using XML-Enabled Technology within the GIDB System Chapter 14: Space Wide Web by Adapters in Distributed Systems Configuration from Reusable Components Chapter 15: XML as a Unifying Framework for Inductive Databases Chapter 16: Designing and Managing an XML Warehouse Chapter 17: XML Management System Benchmarks Chapter 18: The Michigan Benchmark: A Micro-Benchmark for XML Query Performance Diagnostics Chapter 19: A Comparison of Database Approaches for Storing XML Documents Chapter 20: Performance Analysis between an XML-Enabled Database and a Native XML Database Remember the name: eTutorials.org Copyright eTutorials.org 2008-2023. All rights reserved.