Limits...
Adaptive GDDA-BLAST: fast and efficient algorithm for protein sequence embedding.

Hong Y, Kang J, Lee D, van Rossum DB - PLoS ONE (2010)

Bottom Line: Herein, we describe the logic and algorithmic process for a heuristic embedding strategy named "Adaptive GDDA-BLAST." Adaptive GDDA-BLAST is, on average, up to 19 times faster than, but has similar sensitivity to our previous method.Further, data are provided to demonstrate the benefits of embedded-alignment measurements in terms of detecting structural homology in highly divergent protein sequences and isolating secondary structural elements of transmembrane and ankyrin-repeat domains.Together, these advances allow further exploration of the embedded alignment data space within sufficiently large data sets to eventually induce relevant statistical inferences.

View Article: PubMed Central - PubMed

Affiliation: Department of Computer Science and Engineering, The Pennsylvania State University, University Park, Pennsylvania, United States of America.

ABSTRACT
A major computational challenge in the genomic era is annotating structure/function to the vast quantities of sequence information that is now available. This problem is illustrated by the fact that most proteins lack comprehensive annotations, even when experimental evidence exists. We previously theorized that embedded-alignment profiles (simply "alignment profiles" hereafter) provide a quantitative method that is capable of relating the structural and functional properties of proteins, as well as their evolutionary relationships. A key feature of alignment profiles lies in the interoperability of data format (e.g., alignment information, physio-chemical information, genomic information, etc.). Indeed, we have demonstrated that the Position Specific Scoring Matrices (PSSMs) are an informative M-dimension that is scored by quantitatively measuring the embedded or unmodified sequence alignments. Moreover, the information obtained from these alignments is informative, and remains so even in the "twilight zone" of sequence similarity (<25% identity). Although our previous embedding strategy was powerful, it suffered from contaminating alignments (embedded AND unmodified) and high computational costs. Herein, we describe the logic and algorithmic process for a heuristic embedding strategy named "Adaptive GDDA-BLAST." Adaptive GDDA-BLAST is, on average, up to 19 times faster than, but has similar sensitivity to our previous method. Further, data are provided to demonstrate the benefits of embedded-alignment measurements in terms of detecting structural homology in highly divergent protein sequences and isolating secondary structural elements of transmembrane and ankyrin-repeat domains. Together, these advances allow further exploration of the embedded alignment data space within sufficiently large data sets to eventually induce relevant statistical inferences. We show that sequence embedding could serve as one of the vehicles for measurement of low-identity alignments and for incorporation thereof into high-performance PSSM-based alignment profiles.

Show MeSH
Four basic steps of Adaptive GDDA-BLAST.(i) Step 1: Find multiple non-overlapping local alignments. (ii) Step 2: Select seed embedding positions in query sequence. (iii) Step 3: Generate final alignments with seed. (iv) Step 4: Filter out non-significant alignments using coverage and pairwise identity of the alignment.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC2962639&req=5

pone-0013596-g007: Four basic steps of Adaptive GDDA-BLAST.(i) Step 1: Find multiple non-overlapping local alignments. (ii) Step 2: Select seed embedding positions in query sequence. (iii) Step 3: Generate final alignments with seed. (iv) Step 4: Filter out non-significant alignments using coverage and pairwise identity of the alignment.

Mentions: Adaptive GDDA-BLAST works through four basic steps, as shown in Figure 7. First, we find the conserved regions by generating non-overlapping local alignments between the query and the target sequence [30]. We call these partial alignments. Second, for each partial alignment from Step 1, seed-inserting positions are determined. Third, we produce final alignments including the seeds. Finally, we filter out the non-significant alignments, using quality parameters such as the %coverage and %identity of the alignment to the corresponding PSSM.


Adaptive GDDA-BLAST: fast and efficient algorithm for protein sequence embedding.

Hong Y, Kang J, Lee D, van Rossum DB - PLoS ONE (2010)

Four basic steps of Adaptive GDDA-BLAST.(i) Step 1: Find multiple non-overlapping local alignments. (ii) Step 2: Select seed embedding positions in query sequence. (iii) Step 3: Generate final alignments with seed. (iv) Step 4: Filter out non-significant alignments using coverage and pairwise identity of the alignment.
© Copyright Policy
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC2962639&req=5

pone-0013596-g007: Four basic steps of Adaptive GDDA-BLAST.(i) Step 1: Find multiple non-overlapping local alignments. (ii) Step 2: Select seed embedding positions in query sequence. (iii) Step 3: Generate final alignments with seed. (iv) Step 4: Filter out non-significant alignments using coverage and pairwise identity of the alignment.
Mentions: Adaptive GDDA-BLAST works through four basic steps, as shown in Figure 7. First, we find the conserved regions by generating non-overlapping local alignments between the query and the target sequence [30]. We call these partial alignments. Second, for each partial alignment from Step 1, seed-inserting positions are determined. Third, we produce final alignments including the seeds. Finally, we filter out the non-significant alignments, using quality parameters such as the %coverage and %identity of the alignment to the corresponding PSSM.

Bottom Line: Herein, we describe the logic and algorithmic process for a heuristic embedding strategy named "Adaptive GDDA-BLAST." Adaptive GDDA-BLAST is, on average, up to 19 times faster than, but has similar sensitivity to our previous method.Further, data are provided to demonstrate the benefits of embedded-alignment measurements in terms of detecting structural homology in highly divergent protein sequences and isolating secondary structural elements of transmembrane and ankyrin-repeat domains.Together, these advances allow further exploration of the embedded alignment data space within sufficiently large data sets to eventually induce relevant statistical inferences.

View Article: PubMed Central - PubMed

Affiliation: Department of Computer Science and Engineering, The Pennsylvania State University, University Park, Pennsylvania, United States of America.

ABSTRACT
A major computational challenge in the genomic era is annotating structure/function to the vast quantities of sequence information that is now available. This problem is illustrated by the fact that most proteins lack comprehensive annotations, even when experimental evidence exists. We previously theorized that embedded-alignment profiles (simply "alignment profiles" hereafter) provide a quantitative method that is capable of relating the structural and functional properties of proteins, as well as their evolutionary relationships. A key feature of alignment profiles lies in the interoperability of data format (e.g., alignment information, physio-chemical information, genomic information, etc.). Indeed, we have demonstrated that the Position Specific Scoring Matrices (PSSMs) are an informative M-dimension that is scored by quantitatively measuring the embedded or unmodified sequence alignments. Moreover, the information obtained from these alignments is informative, and remains so even in the "twilight zone" of sequence similarity (<25% identity). Although our previous embedding strategy was powerful, it suffered from contaminating alignments (embedded AND unmodified) and high computational costs. Herein, we describe the logic and algorithmic process for a heuristic embedding strategy named "Adaptive GDDA-BLAST." Adaptive GDDA-BLAST is, on average, up to 19 times faster than, but has similar sensitivity to our previous method. Further, data are provided to demonstrate the benefits of embedded-alignment measurements in terms of detecting structural homology in highly divergent protein sequences and isolating secondary structural elements of transmembrane and ankyrin-repeat domains. Together, these advances allow further exploration of the embedded alignment data space within sufficiently large data sets to eventually induce relevant statistical inferences. We show that sequence embedding could serve as one of the vehicles for measurement of low-identity alignments and for incorporation thereof into high-performance PSSM-based alignment profiles.

Show MeSH