Igor Ulitsky, Adi Maron-Katz, Seagull Shavit, Dorit Sagir, Chaim Linhart, Ran Elkon, Amos Tanay, Roded Sharan, Yosef Shiloh, Ron Shamir
Expander: from expression microarrays to networks and functions
Nature Protocols 5 (2),
2010
A major challenge in the analysis of gene expression microarray data
is to extract meaningful biological knowledge out of the huge volume
of raw data. Expander (EXPression ANalyzer and DisplayER) is an integrated
software platform for the analysis of gene expression data, which
is freely available for academic use. It is designed to support all
the stages of microarray data analysis, from raw data normalization
to inference of transcriptional regulatory networks. The microarray
analysis described in this protocol starts with importing the data
into Expander 5.0 and is followed by normalization and filtering.
Then, clustering and network-based analyses are performed. The gene
groups identified are tested for enrichment in function (based on
Gene Ontology), co-regulation (using transcription factor and microRNA
target predictions) or co-location. The results of each analysis
step can be visualized in a number of ways. The complete protocol
can be executed in ≈1 h.
close
@ARTICLE{UMS2010,
author = {Ulitsky, Igor and Maron-Katz, Adi and Shavit, Seagull and Sagir,
Dorit and Linhart, Chaim and Elkon, Ran and Tanay, Amos and Sharan,
Roded and Shiloh, Yosef and Shamir, Ron},
title = {{E}xpander: from expression microarrays to networks and functions},
journal = {Nature Protocols},
year = {2010},
volume = {5},
pages = {303--322},
number = {2},
abstract = {A major challenge in the analysis of gene expression microarray data
is to extract meaningful biological knowledge out of the huge volume
of raw data. Expander (EXPression ANalyzer and DisplayER) is an integrated
software platform for the analysis of gene expression data, which
is freely available for academic use. It is designed to support all
the stages of microarray data analysis, from raw data normalization
to inference of transcriptional regulatory networks. The microarray
analysis described in this protocol starts with importing the data
into Expander 5.0 and is followed by normalization and filtering.
Then, clustering and network-based analyses are performed. The gene
groups identified are tested for enrichment in function (based on
Gene Ontology), co-regulation (using transcription factor and microRNA
target predictions) or co-location. The results of each analysis
step can be visualized in a number of ways. The complete protocol
can be executed in ≈1 h.},
doi = {10.1038/nprot.2009.230},
owner = {raphael},
timestamp = {2010.10.04}
}
close
Ulrich Laube, Markus E. Nebel
Maximum likelihood analysis of algorithms and data structures
Theoretical Computer Science 411 (1),
2010
@ARTICLE{LN2010,
author = {Laube, Ulrich and Nebel, Markus E.},
title = {{M}aximum likelihood analysis of algorithms and data structures},
journal = {Theoretical Computer Science},
year = {2010},
volume = {411},
pages = {188--212},
number = {1},
comment = {02-08},
doi = {10.1016/j.tcs.2009.09.025},
owner = {raphael},
timestamp = {2010.10.04}
}
close
Takuji Yamada, Peer Bork
Evolution of biomolecular networks — lessons from metabolic and
protein interactions
Nature Reviews Molecular Cell Biology 10,
November 2009
@ARTICLE{YamBo2009,
author = {Takuji Yamada and Peer Bork},
title = {{E}volution of biomolecular networks — lessons from metabolic and
protein interactions},
journal = {Nature Reviews Molecular Cell Biology},
year = {2009},
volume = {10},
pages = {791--803},
month = {November},
comment = {01-13},
owner = {raphael},
timestamp = {2010.03.24},
url = {http://www.nature.com/nrm/journal/v10/n11/abs/nrm2787.html}
}
close
David L. Robertson, Simon C. Lovell
Evolution in protein interaction networks: co-evolution, rewiring
and the role of duplication
Biochemical Society Transactions 37,
2009
Molecular function is the result of proteins working together, mediated
by highly specific interactions. Maintenance and change of protein
interactions can thus be considered one of the main links between
molecular function and mutation. As a consequence, protein interaction
datasets can be used to study functional evolution directly. In terms
of constraining change, the co-evolution of interacting molecules
is a very subtle process. This has implications for the signal being
used to predict protein–protein interactions. In terms of functional
change, the ‘rewiring’ of interaction networks, gene duplication
is critically important. Interestingly, once duplication has occurred,
the genes involved have different probabilities of being retained
related to how they were generated. In the present paper, we discuss
some of our recent work in this area.
close
@ARTICLE{RobLo2009,
author = {David L. Robertson and Simon C. Lovell},
title = {{E}volution in protein interaction networks: co-evolution, rewiring
and the role of duplication},
journal = {Biochemical Society Transactions},
year = {2009},
volume = {37},
pages = {768--771},
abstract = {Molecular function is the result of proteins working together, mediated
by highly specific interactions. Maintenance and change of protein
interactions can thus be considered one of the main links between
molecular function and mutation. As a consequence, protein interaction
datasets can be used to study functional evolution directly. In terms
of constraining change, the co-evolution of interacting molecules
is a very subtle process. This has implications for the signal being
used to predict protein–protein interactions. In terms of functional
change, the ‘rewiring’ of interaction networks, gene duplication
is critically important. Interestingly, once duplication has occurred,
the genes involved have different probabilities of being retained
related to how they were generated. In the present paper, we discuss
some of our recent work in this area.},
comment = {01-15},
doi = {10.1042/BST0370768},
keywords = {co-evolution, duplication, protein interaction network, protein–protein
interaction, rewiring},
owner = {raphael},
timestamp = {2010.03.24},
url = {http://www.biochemsoctrans.org/bst/037/0768/bst0370768.htm}
}
close
Franz-Josef Muller, Louise C. Laurent, Dennis Kostka, Igor Ulitsky, Roy Williams, Christina Lu, In-Hyun Park, Mahendra S. Rao, Ron Shamir, Philip H. Schwartz, Nils O. Schmidt, Jeanne F. Loring
Regulatory networks define phenotypic classes of human stem cell
lines
Nature 455,
2008
@ARTICLE{MLK2008,
author = {Muller, Franz-Josef and Laurent, Louise C. and Kostka, Dennis and
Ulitsky, Igor and Williams, Roy and Lu, Christina and Park, In-Hyun
and Rao, Mahendra S. and Shamir, Ron and Schwartz, Philip H. and
Schmidt, Nils O. and Loring, Jeanne F.},
title = {{R}egulatory networks define phenotypic classes of human stem cell
lines},
journal = {Nature},
year = {2008},
volume = {455},
pages = {401--405},
comment = {02-07},
doi = {10.1038/nature07213},
owner = {raphael},
timestamp = {2010.10.04}
}
close
Nizar N. Batada, Laurence D. Hurst, Mike Tyers
Evolutionary and Physiological Importance of Hub Proteins
PLoS Computational Biology 2,
July 2006
@ARTICLE{BaHuT2006,
author = {Nizar N. Batada and Laurence D. Hurst and Mike Tyers},
title = {{E}volutionary and {P}hysiological {I}mportance of {H}ub {P}roteins},
journal = {PLoS Computational Biology},
year = {2006},
volume = {2},
pages = {748--756},
month = {July},
note = {Issue 7, e88},
comment = {01-14},
owner = {raphael},
timestamp = {2010.03.24},
url = {http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1500817/}
}
close
Robin Dowell, Sean Eddy
Evaluation of several lightweight stochastic context-free grammars
for RNA secondary structure prediction
BMC Bioinformatics 5 (1),
2004
BACKGROUND:RNA secondary structure prediction methods based on probabilistic
modeling can be developed using stochastic context-free grammars
(SCFGs). Such methods can readily combine different sources of information
that can be expressed probabilistically, such as an evolutionary
model of comparative RNA sequence analysis and a biophysical model
of structure plausibility. However, the number of free parameters
in an integrated model for consensus RNA structure prediction can
become untenable if the underlying SCFG design is too complex. Thus
a key question is, what small, simple SCFG designs perform best for
RNA secondary structure prediction?
RESULTS:Nine different small SCFGs were implemented to explore the
tradeoffs between model complexity and prediction accuracy. Each
model was tested for single sequence structure prediction accuracy
on a benchmark set of RNA secondary structures.
CONCLUSIONS:Four SCFG designs had prediction accuracies near the performance
of current energy minimization programs. One of these designs, introduced
by Knudsen and Hein in their PFOLD algorithm, has only 21 free parameters
and is significantly simpler than the others.
close
@ARTICLE{DowEd2004,
author = {Robin Dowell and Sean Eddy},
title = {{E}valuation of several lightweight stochastic context-free grammars
for {RNA} secondary structure prediction},
journal = {BMC Bioinformatics},
year = {2004},
volume = {5},
pages = {71},
number = {1},
abstract = {BACKGROUND:RNA secondary structure prediction methods based on probabilistic
modeling can be developed using stochastic context-free grammars
(SCFGs). Such methods can readily combine different sources of information
that can be expressed probabilistically, such as an evolutionary
model of comparative RNA sequence analysis and a biophysical model
of structure plausibility. However, the number of free parameters
in an integrated model for consensus RNA structure prediction can
become untenable if the underlying SCFG design is too complex. Thus
a key question is, what small, simple SCFG designs perform best for
RNA secondary structure prediction?
RESULTS:Nine different small SCFGs were implemented to explore the
tradeoffs between model complexity and prediction accuracy. Each
model was tested for single sequence structure prediction accuracy
on a benchmark set of RNA secondary structures.
CONCLUSIONS:Four SCFG designs had prediction accuracies near the performance
of current energy minimization programs. One of these designs, introduced
by Knudsen and Hein in their PFOLD algorithm, has only 21 free parameters
and is significantly simpler than the others.},
comment = {01-01},
doi = {10.1186/1471-2105-5-71},
issn = {1471-2105},
owner = {raphael},
pubmedid = {15180907},
timestamp = {2010.03.22},
url = {http://www.biomedcentral.com/1471-2105/5/71}
}
close
Markus E. Nebel
Combinatorial Properties of RNA Secondary Structures
Journal of Computational Biology 9,
2001
The secondary structure of a RNA molecule is of great importance and
possesses inuence, e.g. on the interaction of tRNA molecules with
proteins or on the stabilization of mRNA molecules. The classication
of secondary structures by means of their order proved useful with
respect to numerous applications. In 1978 Waterman, who gave the
rst precise formal framework for the topic, suggested to determine
the number a n;p of secondary structures of size n and given order
p. Since then, no satisfactory result has been found. Based on an
observation due to Viennot et al. we will derive generating functions
for the secondary structures of order p from generating functions
for binary tree structures with Horton-Strahler number p. These generating
functions enable us to compute a precise asymptotic equivalent for
a n;p . Furthermore, we will determine the related number of structures
when the number of unpaired bases shows up as an additional parameter.
Our approach proves to be general enough to compute the average order
of a secondary structure together with all the r-th moments and to
enumerate substructures such as hairpins or bulges in dependence
on the order of the secondary structures considered.
close
@ARTICLE{Nebel2001,
author = {Markus E. Nebel},
title = {{C}ombinatorial {P}roperties of {RNA} {S}econdary {S}tructures},
journal = {Journal of Computational Biology},
year = {2001},
volume = {9},
pages = {541--573},
abstract = {The secondary structure of a RNA molecule is of great importance and
possesses inuence, e.g. on the interaction of tRNA molecules with
proteins or on the stabilization of mRNA molecules. The classication
of secondary structures by means of their order proved useful with
respect to numerous applications. In 1978 Waterman, who gave the
rst precise formal framework for the topic, suggested to determine
the number a n;p of secondary structures of size n and given order
p. Since then, no satisfactory result has been found. Based on an
observation due to Viennot et al. we will derive generating functions
for the secondary structures of order p from generating functions
for binary tree structures with Horton-Strahler number p. These generating
functions enable us to compute a precise asymptotic equivalent for
a n;p . Furthermore, we will determine the related number of structures
when the number of unpaired bases shows up as an additional parameter.
Our approach proves to be general enough to compute the average order
of a secondary structure together with all the r-th moments and to
enumerate substructures such as hairpins or bulges in dependence
on the order of the secondary structures considered.},
citeseerurl = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.1643},
comment = {01-04},
owner = {raphael},
timestamp = {2010.03.22},
url = {http://wwwagak.informatik.uni-kl.de/staff/nebel/index.html}
}
close
Ivo L. Hofacker, Peter Schuster, Peter F. Stadler
Combinatorics of RNA Secondary Structures
Discr. Appl. Math 89,
1996
abs
bib
Secondary structures of polynucleotides can be view as a certain class
of planar vertex-labeled graphs. We construct recursion formulae
enumerating various sub-classes of these graphs as well as certain
structural elements (sub-graphs). First order asymptotics are derived
and their dependence on the logic of base pairing is computed and
discussed.
close
@ARTICLE{HoScS1996,
author = {Ivo L. Hofacker and Peter Schuster and Peter F. Stadler},
title = {{C}ombinatorics of {RNA} {S}econdary {S}tructures},
journal = {Discr. Appl. Math},
year = {1996},
volume = {89},
pages = {-},
abstract = {Secondary structures of polynucleotides can be view as a certain class
of planar vertex-labeled graphs. We construct recursion formulae
enumerating various sub-classes of these graphs as well as certain
structural elements (sub-graphs). First order asymptotics are derived
and their dependence on the logic of base pairing is computed and
discussed.},
citeseerurl = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.5965},
comment = {01-02},
owner = {raphael},
timestamp = {2010.03.22}
}
close
T. Huang, K.S. Fu
On Stochastic Context-Free Languages
Information Sciences 3 (3),
1971
abs
bib
In this paper, properties of normalized stochastic languages are discussed
and alternative procedures for constructing the Comsky and Greibach
normal forms for normalized stochastic context-free grammar (nscfg)
are presented. A normalized stochastic context-free language (nscfl)
is defined in terms of a nscfg. Furthermore, stochstic languages
accepted by stochastic pushdown automata (spda) are defined, and
relationships between stochastic context-free languages and spda
are studied. The class of languages accepted by a spda with a 0 cutpoint
is precisely the class of scfl.
close
@ARTICLE{HuaFu1971,
author = {T. Huang and K.S. Fu},
title = {{O}n {S}tochastic {C}ontext-{F}ree {L}anguages},
journal = {Information Sciences},
year = {1971},
volume = {3},
pages = {201--224},
number = {3},
abstract = {In this paper, properties of normalized stochastic languages are discussed
and alternative procedures for constructing the Comsky and Greibach
normal forms for normalized stochastic context-free grammar (nscfg)
are presented. A normalized stochastic context-free language (nscfl)
is defined in terms of a nscfg. Furthermore, stochstic languages
accepted by stochastic pushdown automata (spda) are defined, and
relationships between stochastic context-free languages and spda
are studied. The class of languages accepted by a spda with a 0 cutpoint
is precisely the class of scfl.},
comment = {01-03},
owner = {raphael},
timestamp = {2010.03.22}
}
close
Werner Kuich
On the Entropy of Context-Free Languages
Information and Control 16 (2),
1970
bib
@ARTICLE{Kuich1970,
author = {Werner Kuich},
title = {{O}n the {E}ntropy of {C}ontext-{F}ree {L}anguages},
journal = {Information and Control},
year = {1970},
volume = {16},
pages = {173--200},
number = {2},
owner = {raphael},
timestamp = {2010.03.22}
}
close