Main Tasks of this Year

Today is Jan 30. Time seems so limited. I am not sure it's enough or not for me to complete my graduation in this year. There are four main tasks before I start to compose the dissertation.
First of all, I need to finish my CV today or tomorrow at the latest. Then try to find a job for myself.
Secondly, as the request of my boss, I have to complete another proposal by March. It is for NSFC.
Thirdly, there are three technical report waiting for me to complete. Their contents would be Section 4,5 and 6 in my coming dissertation. Besides, I need to get at least two papers published based on the results of these research.
The last but not the least, compose the dissertation and preparation for the doctoral defense.

One-gene-one-enzyme Hypothesis

One gene one enzyme, this is a hypothesis. It believes that one gene only help to generate one enzyme, because of which this gene determines the specificity of this enzyme and influence its phenotype. It comes from a story of G.W.Beadle and E.L.Taum in 1941.
However, there are some enzymes which are aggregated from several different polypeptides and then caused active. Now it is found that one gene can determine more than one polypeptides, and polypeptides can help to form different enzymes or be members of only one enzyme. Thus, one gene should be corresponded to one specific polypeptide, instead of one enzyme.

Connect to KEGG by KEGGAPI

These two days I spend much time on the codes for connecting KEGG by its API. Fortunately the KEGGAPI is updated to adapt to use AXIS 1.4 version, which means that I don't need to do the pretreatment as described at the website.

Here I write some code according to its Javadoc. Having got all the ports opened, it runs pretty well. Thus I know where the previous problem is: The remote machine doesn't allow the script out because only the port 3128 is open.


package org.tingting.bn.mn.networkbuilder.test;

import org.tingting.bn.mn.networkbuilder.domain.KeggConnector;

import keggapi.Definition;
import keggapi.KEGGPortType;

public class TestKeggConnector {

/**
* @param args
*/

public static void main(String[] args){

KeggConnector conn = new KeggConnector();
KEGGPortType serv;

try{
serv = conn.getServ();
Definition result[] = serv.list_pathways("hsa");

for( int i = 0; i <>

Perl is useful too

I subscribed the mail lists of china-pm and bio-perl-pm. Actually I didn't look into it very carefully until just now. Some guys introduce the use of perl to develop the plug-in for firefox, which shocks me a lot. Perl can be used to such a high level, but I give it up. Anyway, regret is useless. Try to grasp both Perl and Java. Be a good programmer soon.

To Be Creative

A good programmer is not always Using the codes of others, rearranging them and modifying them, but do some creative work. Create the methods and codes of their own, for others.

I want to and will be such a good programmer later.

Some interesting website

Today when I am surfing online, I found some website very interesting.
First, metabolicvisualizer, very creative website. It lets you control the contents of the involved elements, such as glucose, ATP, and so on. With your adjusting, the reactions inside the big cycle area are automatically adjusted. Very interesting.

Second, DAVID, The Database for Annotation, Visualization and Integrated Discovery. DAVID now provides a comprehensive set of functional annotation tools for investigators to understand biological meaning behind large list of genes.

A paper published in Nature Protocols describes step-by-step procedure to use DAVID:

Systematic and integrative analysis of large gene lists using DAVID Bioinformatics Resources. (2009) Nat. Protoc. 4:44 -57.

http://www.nature.com/nprot/journal/v4/n1/abs/nprot.2008.211.html

Note: This paper, commissioned by the Nature-branded journal -- Nature Protocols, systematically describes the rationals and procedures to use the DAVID Bioinformatics tools. By following the step-by-step procedure in the paper, readers will be able to more efficiently use DAVID bioinformatics tools for high-throughput gene functional analysis, leading to more meaningful analytic experiences and maximal satisfactory results. In this moment, subscription to Natrue web site is required to view full text. We will provide free archive-version of the paper shortly.

Using Network Alignment to serve the discovery of undealying disease

In the recent reports, the most question which was thrown to me is, what the hell of designing a network comparison algorithm can be used to? Now, Xuebing Wu et al. help me to give one answer: network alignment can be used to detect or predict the underlying disease families. (The other applications include reconstructing the phylogenetic relationships of organisms, integrating data of genome and proteome, querying the interested pathway within the known pathway databases, and so on.)

Here is the link of this paper: http://bioinformatics.oxfordjournals.org/cgi/content/short/25/1/98?. Thank Samuel for helping download it.

Mahalanobis Distance

Just now I saw a paper named

Using Mahalanobis distance to compare genomic signatures between bacterial plasmids and chromosomes

on Nucleic Acids Research.

To say the truth, I don't care what the paper are studying, but Mahalanobis distance grasped my eyesights as soon as I saw this title. What's Mahalanobis distance? I know nothing about it before.

In Chinese it is usually translated into "马哈朗诺比斯距离(马氏距离)"。Here is something helpful from someone's blog. (From: http://rogerdhj.blog.sohu.com/39020502.html )

定义：p维空间的两点（两个p维向量x,y）的距离定义为：

并且点x欧氏模数为：

这里很快可以得出，所有到原点距离相等的点满足

这是某个正球体的方程。这就是说观测数据x的各个分量对x至中心的欧式距离贡献是相等的。然而在统计学中我们希望寻求这样一种距离，它的各个分量的作用程度是不同的。差别较大的分量应该接受较小的权重。

如

然后定义x,y之间的距离

这里

现在x的模数等于

所有到原点等距离的点满足

这是以原点为中心的某个椭球体的方程。

Very clear, right? But please note the essential point of Mahalanobis Distance: The bigger the component of distance between two objects is, the smaller the corresponding weights should be.


Here is an example for application of Mahalanobis Distance on detecting the odd values. (From: http://nanapple.happy.blog.163.com/blog/static/77501222200883945195/)

之所以把它们称为异常值，是因为它们与众不同，远离大部分数据。它们有可能是一些错误数据，将会破坏您的分析结果。或者它们有可能是一些真实存在的现象，正在等待您的发现和理解，以便进行一些精彩的应用。无论是哪一种情况，您都应该重视它们。

对于一维数据 -- 他们只是一些极端值，很容易被发现。

	对于二维数据 -- 异常值在一些偏僻的方向延伸出来。如果变量具有相关性，那您会看到异常值在二维的方向延伸出来，而不是在某个维度分别延伸出来。您可以通过测量该点与正态分布云图的偏离距离来量化它的偏移。该距离称为马哈朗诺比斯距离（Mahalanobis distance）。

对于三维数据 -- 三维旋转图用于发现三维的异常值。如果您的数据变量多于三维，那您不得不使用其它的技术。如果您的数据变量都具有相关性， 您将可以看到您的数据有着一定的延伸方向。同时您可以看到异常值从偏僻的方向延伸出来。所以您可以选取三个主要变量来制作三维旋转图，以发现异常值。

考虑N维的情况 另一方面，您可以考虑整个相关矩阵，为每一个观测计算其马哈朗诺比斯距离。再从多元均值中得到N维的距离。但是这样一来，所有的观测，变量，包括被测量值 本身都会被考虑进去，这使得测量出的距离与被测量值具有相关性，影响结果的准确性。所以在这种情况下，使用折叠距离（Jackknifed distance)会更好 -- 每一点将与不包含该点的观测进行距离测量。

　

如果您正在拟合模型，您可能会想知道每一个观测对结果的影响。此时您可以使用杠杆图（Leverage plot)。它将显示某个观测的残差以及该残差对模型所造成的影响。如果您希望从数据中发现潜在信息，灵活运用JMP强大的图形工具绝对会对您有很大的帮助。

Seems there are still a lot of novel distance definition which is unknown to me. Let me think it over, what this distance can help me in my research?

The Basic Knowledge on Random Forest

In machine learning, a random forest is a classifier that consists of many decision trees and outputs the class that is the mode of the classes output by individual trees. The algorithm for inducing a random forest was developed by Leo Breiman and Adele Cutler. The term came from random decision forests that was first proposed by Tin Kam Ho of Bell Labs in 1995. The method combines Breiman's "bagging" idea and Ho's "random subspace method" to construct a collection of decision trees with controlled variations.

Learning Algorithm
Each tree is constructed using the following algorithm:
1. Let the number of training cases be N, and the number of variables in the classifier be M. (假设有N个训练样本，M个变量)
2. We are told the number m of input variables to be used to determine the decision at a node of the tree; m should be much less than M. （给定m个输入变量，用来确定树上一个节点的决策，m应小于M）
3. Choose a training set for this tree by choosing N times with replacement from all N available training cases(i.e. take a bootstrap sample)。 Use the rest of the cases to estimate the error of the tree, by predicting their classes.（从N个训练样本中随机重复取样N次得到一组训练集，即bootstrap取样）。预测剩余样本的类别，并用以估计决策树的误差。
4. For each node of the tree, randomly choose m variable on which to base the decision at that node. Calculate the best split based on these m variable in the training set.（对每个节点都随机选取m个基于此节点决策的变量。根据着m个变量计算其最佳分割方式）
5. Each tree is fully grown and not pruned(as may be done in constructing a normal tree classifier). （每棵树都会完整生长，不会像其他许多正常树分类器构建完成后经常做的那样被剪枝）

Advantages
The advantages of random forest are:

• For many data sets, it produces a highly accurate classifier (分类准确度高)
  
• It handles a very large number of input variables (处理大量输入变量)
  
• It estimates the importance of variables in determine classification(在决策类别时，评估变量的重要性)
• It generates an internal unbiased estimate of the generalization error as the forest building progresses(在构建森林过程中产生对泛化误差的内部无偏差估计)
• It includes a good method for estimating missing data and maintains accuracy when a large proportion of the data are missing （具有一个比较好的方法可以估计缺失值，并且如果有一大部分数据缺失，它仍可以维持准确度）
  
• It provides an experimental way to detect variable interactions（提供一种试验方法侦测变量之间的相互作用）
• It can balance error in class population unbalanced data sets（对于非平衡数据集中的分类数据，可以平衡误差）
• It computes proximities between cases, useful for clustering, detecting outliers, and(by scaling) visualizing the data(计算各种用例之间的相似性，对于聚类、侦测离群值和数据可视化（扩大或缩小）都非常游泳)
• Using the above, it can be extended to unlabeled data, leading to unsupervised clustering, outlier detection and data views （它也可被拓展到无标记数据的应用，形成非监督聚类、侦测离群值和数据可视化的方法）
  
• Learning is fast.（学习过程很快）

Reference:
Wiki for Random Forest
中文
Random Forest from Berkeley
RandomForest on the main page of Breiman

The graph representation in JUNG

1. Network and graph data sets have often been described mathematically as matrices which are commonly implemented as 2D arrays. The represantation facilitates fast retrieval of the edges, which operations is called findEdge in JUNG.
However, this representation is generally not feasible for large-scale networks. First, it requires O(|V|2) space. Second, existing algorithms for network analysis, which involve matrix multiplication or matrix inversion, generally require O(|V|3) time on 2D arrays. Third, this representation is problematic for dynamic networks(those whose vertex set may grow larger or smaller) and for networks with parallel edges. Finally, large-scale networks are almost invariably very sparse, so almost all the the space in a 2D array representing such a network is wasted on representing absent links.
2. A common alternative representation for sparse graphs and networks is the adjacency list representation, in which each vertex maintains a list of incident edges (or adjacent vertices); this requires O(|V|+|E|) space. This representation does NOT permit an efficient implementation of findEdge.
3. Most of the current JUNG vertex implementations employ a variant of the adjacency list representation, which is termed as adjacency map representation: each vertex maintains a map from each adjacent vertex to the connecting edge(or connecting edge set, in the case of graphs that permit parallel edges). ( Separate maps are maintained, if appropriate, for incoming directed edges, outgoing directed edges, and undirected edges.) This uses slightly more memory than the adjacency list representation, but makes findEdge approximately as fast as the corresponding operation on the 2D array representation.

Why choose JUNG?

1. How is JUNG different from...

   1. ... UCINET?

      UCINET is a widely-used application among social networks researchers for performing standard social network analysis techniques to graphs.
      However, UCINET cannot be embedded into applications: you can't call UCINET in an end-user display.
      JUNG provides facilities to dynamically change graphs, to programatically call code, and to output the results as the program continues.

   2. ... PAJEK?

      PAJEK is a stand-alone tool for visualizing and analyzing networks. JUNG provides many algorithms that PAJEK does not (and, currently vice versa), and--as noted for UCINET--is easily incorporated into network applications.
      JUNG is capable of both reading and writing simple PAJEK-format files. (JUNG's PAJEK file reader does not currently support the entire PAJEK file format.)

   3. ... R? http://www.r-project.org

      R is a specialized programming language geared primarily toward the statistics community, offering a broad set of statistical routines. JUNG is intended for a less-specialized audience, and, as a pure JAVA solution, is embeddable within web browsers and pre-existing applications.

   4. ... GFC? http://www.alphaworks.ibm.com/tech/gfc

      GFC is a graph drawing-oriented package released by IBM. It is specific to using Java's AWT/Swing, and contains few graph manipulation algorithms.

   JUNG is open-source, free, and has a wide variety of algorithms available. Better, it's easily extensible through a widely-documented API: if it's not there yet, you can add it yourself.

2. What types of graphs does JUNG support?

JUNG supports graphs, general k-partite graphs (of which bipartite graphs are a special case), hypergraphs, and has limited support for trees.

KEGG API or Pathway.xsd?

The first step of my work is to reconstruct the metabolic network.

Previously, we use Perl to extract the enzyme information from the LIGAND database of KEGG as well as the excel sheets of the Ma and Zeng database. (The latter is also based on KEGG, which should be noticed.)

Now I plan to build the whole project on the basis of Java. The first step is using the KEGG API to help reconstruct the organism-specific metabolic networks(graphs).

I can either try to use KEGG API to reconstruct the network or use the pathway.xsd which Samuel did for me before. Which one should I use?

(Sometimes I regretted a little that I gave up Perl and turned to Java. The latter is really a challenge for me, because the history that I was fear of the object-oriented programming can be tracked back to nearly 10 years ago. Anyway, I have started with it. Then don't think too much and do not always worry about the graduation. Learn it step by step, and I must be a good programmer soon.)

1. KEGG API:
Here is the description on the KEGG Java Page.


Here is the steps to get KEGG-API ready.

1. Download the axis package(Now the latest version is axis-1.4-final).
2. Download the axisfix.pl to generate the classes for KEGGAPI. This perl file is to fix the KEGGBindingStuf.java generated by axis. Here is the code, very simple. Delete all the text "org.apache.axis.uitls;" and "org.apache.axis.soap;" and if the there is a line who starts with 'package' then add the sentences "import org.apache.axis.utils.*;(enter)" and "import org.apache.axis.soap.*;(enter)" in the file.
   



#!/usr/bin/perl -i
# script to fix KEGGBindingStub.java generated by axis-1_2alpha
while (<>) {
s/org\.apache\.axis\.utils\.//;
s/org\.apache\.axis\.soap\.//;
print;
if (/^package/) {
print "import org.apache.axis.utils.*;\n";
print "import org.apache.axis.soap.*;\n";
}
}




3. Now the api is ready for use.

---

However, do remember that KEGG API just provides a web service. If you have no available internet connection, you cannot run your project maybe. Okay, let's see another way, which is to use jaxb and *.xsd to parse the pathway xml files provided by KEGG.


Thank Samuel help me to write pathway.xsd for me. This file is right to parse the KEGG xml files. Follow the steps to make it ready for your project:

1. Download and include the jaxb into the user library
2. Go to jaxb\bin and put pathway.xsd into this folder
3. Under the cmd command line, run xjc pathway.xsd
4. Done.

Yes, the answer is pathway.xsd.