Show simple item record

dc.creatorAbnousi, Armen
dc.creatorBroschat, Shira L.
dc.creatorKalyanaraman, Ananth
dc.description.abstractBackground: Identifying conserved regions in protein sequences is a fundamental operation, occurring in numerous sequence-driven analysis pipelines. It is used as a way to decode domain-rich regions within proteins, to compute protein clusters, to annotate sequence function, and to compute evolutionary relationships among protein sequences. A number of approaches exist for identifying and characterizing protein families based on their domains, and because domains represent conserved portions of a protein sequence, the primary computation involved in protein family characterization is identification of such conserved regions. However, identifying conserved regions from large collections (millions) of protein sequences presents significant challenges. Methods: In this paper we present a new, alignment-free method for detecting conserved regions in protein sequences called NADDA (No-Alignment Domain Detection Algorithm). Our method exploits the abundance of exact matching short subsequences (k-mers) to quickly detect conserved regions, and the power of machine learning is used to improve the prediction accuracy of detection. We present a parallel implementation of NADDA using the MapReduce framework and show that our method is highly scalable. Results: We have compared NADDA with Pfam and InterPro databases. For known domains annotated by Pfam, accuracy is 83%, sensitivity 96%, and specificity 44%. For sequences with new domains not present in the training set an average accuracy of 63% is achieved when compared to Pfam. A boost in results in comparison with InterPro demonstrates the ability of NADDA to capture conserved regions beyond those present in Pfam. We have also compared NADDA with ADDA and MKDOM2, assuming Pfam as ground-truth. On average NADDA shows comparable accuracy, more balanced sensitivity and specificity, and being alignment-free, is significantly faster. Excluding the one-time cost of training, runtimes on a single processor were 49s, 10,566s, and 456s for NADDA, ADDA, and MKDOM2, respectively, for a data set comprised of approximately 2500 sequences.en_US
dc.rightsCreative Commons Attribution 4.0 International
dc.titleA Fast Alignment-Free Approach for De Novo Detection of Protein Conserved Regions
dc.description.versionPublished copy
dc.description.citationKhaledian, E., K. A. Brayton, and S. L. Broschat. (2020). A systematic approach to bacterial phylogeny using order-level sampling with identification of HGT using network science. Microorganisms, Vol. 8, No. 2, 312. doi:10.3390/microorganisms8020312. PMCID: PMC7074868.

Files in this item


This item appears in the following Collection(s)

  • Broschat, Shira
    This collection features research and educational materials by Shira Broschat, Professor and Curriculum Coordinator for the School of Electrical Engineering and Computer Science at Washington State University.

Show simple item record

Creative Commons Attribution 4.0 International
Except where otherwise noted, this item's license is described as Creative Commons Attribution 4.0 International