title: Sequence-based classification using discriminatory motif feature selection.
abstract: Most existing methods for sequence-based classification use exhaustive feature generation, employing, for example, all k-mer patterns. The motivation behind such (enumerative) approaches is to minimize the potential for overlooking important features. However, there are shortcomings to this strategy. First, practical constraints limit the scope of exhaustive feature generation to patterns of length ≤ k, such that potentially important, longer (> k) predictors are not considered. Second, features so generated exhibit strong dependencies, which can complicate understanding of derived classification rules. Third, and most importantly, numerous irrelevant features are created. These concerns can compromise prediction and interpretation. While remedies have been proposed, they tend to be problem-specific and not broadly applicable. Here, we develop a generally applicable methodology, and an attendant software pipeline, that is predicated on discriminatory motif finding. In addition to the traditional training and validation partitions, our framework entails a third level of data partitioning, a discovery partition. A discriminatory motif finder is used on sequences and associated class labels in the discovery partition to yield a (small) set of features. These features are then used as inputs to a classifier in the training partition. Finally, performance assessment occurs on the validation partition. Important attributes of our approach are its modularity (any discriminatory motif finder and any classifier can be deployed) and its universality (all data, including sequences that are unaligned and/or of unequal length, can be accommodated). We illustrate our approach on two nucleosome occupancy datasets and a protein solubility dataset, previously analyzed using enumerative feature generation. Our method achieves excellent performance results, with and without optimization of classifier tuning parameters. A Python pipeline implementing the approach is available at http://www.epibiostat.ucsf.edu/biostat/sen/dmfs/.
authors.affiliation: Department of Epidemiology and Biostatistics, University of California San Francisco, San Francisco, California, United States of America. hao@biostat.ucsf.edu
authors.forename: Hao
authors.initials: H
authors.lastname: Xiong
authors.forename: Daniel
authors.initials: D
authors.lastname: Capurso
authors.forename: Saunak
authors.initials: S
authors.lastname: Sen
authors.forename: Mark R
authors.initials: MR
authors.lastname: Segal
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs; D006801:Humans; D009707:Nucleosomes / Q000737:chemistry* / Q000145:classification*; D011506:Proteins / Q000737:chemistry* / Q000145:classification*; D016415:Sequence Alignment; D012984:Software
chemical_list: D009707:Nucleosomes; D011506:Proteins
references.citation: Bioinformatics. 1999 Jul-Aug;15(7-8):563-77
references.pmid: 10487864
references.citation: Nucleic Acids Res. 2005 Jul 1;33(Web Server issue):W412-6
references.pmid: 15980501
references.citation: Nucleic Acids Res. 2007 Jan;35(Database issue):D193-7
references.pmid: 17142230
references.citation: J Mol Biol. 1998 Sep 4;281(5):827-42
references.pmid: 9719638
references.citation: PLoS Genet. 2006 Mar;2(3):e26
references.pmid: 16520826
references.citation: Bioinformatics. 2007 Jun 1;23(11):1321-30
references.pmid: 17267435
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2011 Mar-Apr;8(2):441-51
references.pmid: 21233524
references.citation: BMC Bioinformatics. 2009 Dec 22;10:442
references.pmid: 20028554
references.citation: BMC Bioinformatics. 2007 Oct 15;8:385
references.pmid: 17937785
references.citation: Bioinformatics. 2004 Mar 1;20(4):467-76
references.pmid: 14990442
references.citation: Curr Opin Genet Dev. 2002 Apr;12(2):249-51
references.pmid: 11915846
references.citation: Bioinformatics. 2011 Apr 1;27(7):1017-8
references.pmid: 21330290
references.citation: Protein Eng Des Sel. 2005 Apr;18(4):175-80
references.pmid: 15849216
references.citation: Pac Symp Biocomput. 2002;:564-75
references.pmid: 11928508
references.citation: J Comput Biol. 2010 May;17(5):733-43
references.pmid: 20500024
references.citation: EURASIP J Bioinform Syst Biol. 2007;:13853
references.pmid: 18340376
references.citation: Arch Microbiol. 2010 Mar;192(3):151-5
references.pmid: 20127480
references.citation: Bioinformatics. 2009 Dec 1;25(23):3181-2
references.pmid: 19773334
references.citation: Bioinformatics. 2011 May 1;27(9):1231-8
references.pmid: 21372086
references.citation: Trends Genet. 2000 Jun;16(6):276-7
references.pmid: 10827456
references.citation: Nucleic Acids Res. 2000 Jan 1;28(1):235-42
references.pmid: 10592235
references.citation: Bioinformatics. 2004 Nov 1;20(16):2860-2
references.pmid: 15130928
references.citation: Genome Biol. 2006;7(6):R49
references.pmid: 16787547
references.citation: Nat Genet. 2007 Oct;39(10):1235-44
references.pmid: 17873876
references.citation: FEBS Lett. 2005 May 23;579(13):2878-82
references.pmid: 15878553
references.citation: Genome Res. 2007 Jun;17(6):928-39
references.pmid: 17568008
references.citation: Proc Natl Acad Sci U S A. 2000 Aug 29;97(18):10096-100
references.pmid: 10944202
references.citation: Nat Biotechnol. 2005 Jan;23(1):137-44
references.pmid: 15637633
references.citation: Science. 1993 Oct 8;262(5131):208-14
references.pmid: 8211139
references.citation: Bioinformatics. 2009 Aug 15;25(16):2126-33
references.pmid: 19389732
references.citation: Genome Biol. 2010;11(11):140
references.pmid: 21118582
references.citation: Bioinformatics. 2009 Sep 1;25(17):2200-7
references.pmid: 19549632
references.citation: Nat Rev Genet. 2005 Feb;6(2):95-108
references.pmid: 15716906
references.citation: Nucleic Acids Res. 1997 Sep 1;25(17):3389-402
references.pmid: 9254694
references.citation: Bioinformatics. 2005 Jun;21 Suppl 1:i369-77
references.pmid: 15961480
references.citation: Bioinformatics. 2008 Jul 1;24(13):i6-14
references.pmid: 18586746
references.citation: Bioinformatics. 2007 Dec 15;23(24):3320-7
references.pmid: 17989092
references.citation: Nucleic Acids Res. 2003 Jul 1;31(13):3586-8
references.pmid: 12824371
references.citation: Stat Appl Genet Mol Biol. 2008;7(1):Article14
references.pmid: 18454729
references.citation: BMC Bioinformatics. 2007;8 Suppl 10:S7
references.pmid: 18269701
references.citation: BMC Bioinformatics. 2005 Dec 29;6:310
references.pmid: 16381612
references.citation: PLoS Comput Biol. 2008 Aug 22;4(8):e1000134
references.pmid: 18725940
references.citation: BMC Bioinformatics. 2006 Mar 20;7 Suppl 1:S9
references.pmid: 16723012
references.citation: Nat Biotechnol. 2007 Feb;25(2):244-8
references.pmid: 17220878
references.citation: J Mol Biol. 2000 Mar 10;296(5):1205-14
references.pmid: 10698627
references.citation: PLoS Comput Biol. 2006 Sep 1;2(9):e113
references.pmid: 16948528
references.citation: Nat Rev Genet. 2009 Mar;10(3):161-72
references.pmid: 19204718