Extracting biologically significant patterns from short time series gene expression data.
BACKGROUND
Time series gene expression data analysis is used widely to study the dynamics of various cell processes. Most of the time series data available today consist of few time points only, thus making the application of standard clustering techniques difficult.


RESULTS
We developed two new algorithms that are capable of extracting biological patterns from short time point series gene expression data. The two algorithms, ASTRO and MiMeSR, are inspired by the rank order preserving framework and the minimum mean squared residue approach, respectively. However, ASTRO and MiMeSR differ from previous approaches in that they take advantage of the relatively few number of time points in order to reduce the problem from NP-hard to linear. Tested on well-defined short time expression data, we found that our approaches are robust to noise, as well as to random patterns, and that they can correctly detect the temporal expression profile of relevant functional categories. Evaluation of our methods was performed using Gene Ontology (GO) annotations and chromatin immunoprecipitation (ChIP-chip) data.


CONCLUSIONS
Our approaches generally outperform both standard clustering algorithms and algorithms designed specifically for clustering of short time series gene expression data. Both algorithms are available at http://www.benoslab.pitt.edu/astro/.
Tchagang
Alain B
AB
Department of Computational Biology, University of Pittsburgh, Pittsburgh, PA 15260, USA. abt10@pitt.edu
Bui
Kevin V
KV
McGinnis
Thomas
T
Benos
Panayiotis V
PV
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D030541:Databases, Genetic; D015870:Gene Expression; D020869:Gene Expression Profiling; D016247:Information Storage and Retrieval / Q000379:methods*; D010363:Pattern Recognition, Automated / Q000379:methods*
J Comput Biol. 2003;10(3-4):341-56
12935332
J Comput Biol. 2000;7(3-4):601-20
11108481
Mol Cell Biol. 1997 Jul;17(7):3640-8
9199298
Proc Int Conf Intell Syst Mol Biol. 2000;8:93-103
10977070
Mol Syst Biol. 2007;3:74
17224918
Bioinformatics. 2003;19 Suppl 1:i255-63
12855468
Bioinformatics. 2003 May 1;19(7):834-41
12724293
Appl Bioinformatics. 2003;2(1):35-45
15130832
IEEE/ACM Trans Comput Biol Bioinform. 2004 Jan-Mar;1(1):24-45
17048406
Science. 2002 Sep 27;297(5590):2270-5
12351791
Proc Natl Acad Sci U S A. 2002 Jul 9;99(14):9121-6
12082179
Mol Biol Cell. 2000 Dec;11(12):4241-57
11102521
Mol Biol Cell. 1998 Dec;9(12):3273-97
9843569
Nat Genet. 1999 Jul;22(3):281-5
10391217
Proc Natl Acad Sci U S A. 1999 Mar 16;96(6):2907-12
10077610
Bioinformatics. 2001 Sep;17(9):763-74
11590094
Nucleic Acids Res. 2004 Jan 22;32(2):447-55
14739237
Proc Natl Acad Sci U S A. 2002 Nov 12;99(23):15136-41
12411577
Nature. 2004 Sep 2;431(7004):99-104
15343339
Proc Natl Acad Sci U S A. 2001 May 8;98(10):5631-6
11344303
Bioinformatics. 2002 Nov;18(11):1477-85
12424119
Nucleic Acids Res. 2004 Jan 1;32(Database issue):D258-61
14681407
Bioinformatics. 2005 Jun;21 Suppl 1:i159-68
15961453
Ernst Schering Res Found Workshop. 2002;(38):83-108
12061008
J Comput Biol. 2003;10(3-4):373-84
12935334
Proc Natl Acad Sci U S A. 1998 Dec 8;95(25):14863-8
9843981
Genes Dev. 2004 Oct 15;18(20):2491-505
15466158
BMC Bioinformatics. 2006 Apr 05;7:191
16597342