extfieldsofstudy:
Computer Science
Mathematics

text:
Search Algorithms for Conceptual Graph Databases

We consider a database composed of a set of conceptual graphs. Using conceptual graphs and graph homomorphism it is possible to build a basic query-answering mechanism based on semantic search. Graph homomorphism defines a partial order over conceptual graphs. Since graph homomorphism checking is an NP-Complete problem, the main requirement for database organizing and managing algorithms is to reduce the number of homomorphism checks. Searching is a basic operation for database manipulating problems. We consider the problem of searching for an element in a partially ordered set. The goal is to minimize the number of queries required to find a target element in the worst case. First we analyse conceptual graph database operations. Then we propose a new algorithm for a subclass of lattices. Finally, we suggest a parallel search algorithm for a general poset. Keywords. Conceptual Graph, Graph Homomorphism, Partial Order, Lattice, Search, Database.

Introduction
Knowledge representation and reasoning has been recognized as a central issue in Artificial Intelligence. Knowledge can be represented symbolically in many ways. One of these ways, called conceptual graph (CG) representation, is graph formalism, that is, knowledge is represented by labelled graphs, and reasoning mechanism is based on graph homomorphism. All kinds of knowledge -ontology, facts, rules and constraints -can be represented by conceptual graphs. In this paper, we consider a database composed of a set of conceptual graphs, representing some assertions about a modelled world. Using conceptual graphs and graph homomorphism a basic queryanswering mechanism can be built based on semantic search. A query made to this base is itself a conceptual graph. An element f of the database is a real answer candidate for query q if and only if there is a homomorphism from q to f. We note that graph homomorphism checking is an NP-Complete problem, that is, homomorphism check is an expensive operation. Therefore the main requirement for conceptual graph database organizing and managing algorithms is to reduce the number of homomorphism checks. Graph homomorphism defines a partial order over conceptual graphs. A finite poset (of CGs) can be considered a database model for a conceptual graph database. Ordering, updating and retrieval are the main operations of organizing and managing of CG databases. All these operations can be represented by the more basic operations: Searching and Finding Parents/Children. In this paper we consider the searching operation only. The problem of searching in partially ordered sets has recently received considerable attention. Motivating this research are practical problems in filesystem synchronization, software testing, information retrieval, and so on. In practical applications, the elements of partially ordered sets can be complicated and comparison of elements may be expensive. In the conceptual graph case, comparison of elements is equivalent to graph homomorphism check. Since graph homomorphism is an NP-Complete problem, CG comparison takes a lot of time and there is no hope to reduce this time. Therefore the efficiency of a search algorithm depends directly on the number of CG comparisons.
The binary search technique is a fundamental method for finding an element in a totally ordered set. As in the totally ordered case, the goal is to minimize the number of queries required to find a target element in the worst case. First we analyse conceptual graph database operations. Then we propose a new algorithm for a subclass of lattices. Finally, we suggest a parallel search algorithm for a general poset. ___________________________________________________________________________ *This research is sponsored in part by the Science Fund Grant 06-03-04-SF0032 from MOSTI, Malaysia

Related Works
Conceptual graphs constitute formalism for knowledge representation. Conceptual graphs were introduced by Sowa [1] as a combination of existential graphs (Peirce, 1909) and semantic networks (Richens, 1956). The first book on conceptual graphs [2] applied them to a wide range of topics in artificial intelligence, computer science, and cognitive science. Since 1991, Conceptual Graphs have been mathematically developed by Chein and Mugnier [3]. One of the main requirements for knowledge representation formalism is to be logically founded, which should have two essential properties with respect to deduction in the target logic: soundness and completeness. For conceptual graphs the equivalent logic is First Order Logic (FOL). The FOL semantic was defined in [2], and the soundness of conceptual graph homomorphism with respect to logical deduction was shown. The first proof of the completeness result, based on the resolution method, is given by Chein and Mugnier [4]. The NP-Completeness of conceptual graph homomorphism checking was proven in [4]. Several algorithms have been proposed for checking conceptual graph homomorphism [5][6][7][8][9]. The simplest case of a partially ordered set is a totally ordered set. The binary search technique is an optimal algorithm for finding an element in a totally ordered set [10]. In [11], Mozes, Onak, and Weimann present a linear-time algorithm that finds the optimal strategy for searching a tree-like partially ordered set. Levinson [12] and Ellis [13] have proposed several modifications of breadth/depth first search technique using some simple properties of partially ordered sets. Dereniowski [14] proves that finding an optimal search strategy for general posets is hard and gives a polynomial-time approximation algorithm with sublogarithmic approximation ratio. In [15], a sorting problem in a partially ordered set is studied.

Partially Ordered Set (Poset) Definition.
A partial order is a binary relation over a set which is reflexive, antisymmetric, and transitive, that is, for all and in , we have that: (i) (reflexivity); (ii) if and then (antisymmetry); (iii) if and then (transitivity). A set with a partial order is called a partially ordered set or poset ( ). For any two elements and of a poset we use if . Also we use ( ) if ( ) and . Let be a poset. If such that , , then is called the top element of (the bottom element ⊥ is dually defined); a poset does not necessarily have a top (bottom) element, but if it has a top (bottom) element then it is unique. Let be a poset and be any non-empty, finite subset of , | | , where is a positive integer. We note that is also a poset. Let be an element of : . The following definitions are useful for future description.
, and for an element of , and respectively.

Representation of Posets
The list of ancestors is dually defined.

Lattice Definition.
A lattice is a partially ordered set in which any two elements have a unique least upper bound (also called the join) and a unique greatest lower bound (also called the meet).
be a finite lattice. An element L j  is join-irreducible if j has exactly one child.

Definitions
A conceptual graph is a labeled bipartite multigraph. One set of nodes is called the set C of concept nodes, and the other set R is called the set of relation nodes. If a concept is the -th argument of a relation then there is an edge between and that is labeled . Concept and relation nodes are labeled by two partially ordered sets. These pair of partially ordered sets is called vocabulary. An edge labeled i between a relation r and a concept c is denoted R , which preserves edges and may decrease concept and relation labels, that is: Let and be two CGs defined over the same vocabulary. We say if there is a homomorphism from to . It is easy to show that the introduced order is transitive and reflexive, but it is not antisymmetric. Definition. Two CGs and are said to be hom-equivalent if and , also denoted . Let G and H be two hom-equivalence classes of CGs defined over the same vocabulary. We say G H if for some G and H . It is clear that it does not matter how and are chosen from G and H, they can be any representatives of respective hom-equivalence classes. We note that the introduced order is a partial order. Let be the set of all hom-equivalence classes of CGs defined over a given vocabulary. Let be a non-empty finite subset of . Without loss of generality, we can consider a set of representatives of elements of Δ. We call it a CG dataset. We note that a CG dataset is also a partially ordered set. Let be any element of , , and let q be any representative of Q, . We call q a query element. A query comparison is a comparison between query element and an element of a dataset. Only query comparison needs to check graph homomorphism, but comparison of two elements of a dataset can be done without graph homomorphism.

Organizing and Managing Operations
There are three main operations: Ordering, Updating and Retrieval. We note that since a CG database is a knowledgebase, the inference operation can be also considered. However we limit ourselves to the first three operations. It is clear that Ordering (generating initial dataset) is consecutively Inserting of query CG into dataset. Updating can be done using Inserting and Deleting of query CG. Retrieval uses only Finding Descendants of query CG. Next representations look like:  Deleting = Searching + something;  Inserting = Finding Parents + Finding Children + something;  Finding Descendants = Finding Children + something. It can be easily checked that the "something" parts of the above representations do not depend on query comparisons and take insignificant time. Finding Parents and Finding Children are dual operations.
Therefore only two operations -Searching and Finding Parents/Children -are enough for manipulating a CG database. We consider only the Searching operation in a poset. The formal definition of the Searching problem can be seen in the input-output part of Algorithm 2.

Searching in Matryoshka-Lattices
There are different classes of posets. We can order poset classes according to how easy they are to search: 1. Totally ordered sets (chains); 2. Tree-like posets; 3. Lattices; 4. General posets. In Figure 1 you can see examples of each class of posets. It is clear that for the searching operation the most amenable class is chains. Existing works show that the next best class is tree-like posets, then lattices, and the worst class is general posets. In the conceptual graph case we usually have lattices or general posets.  , y x  if and only if the binary code of x is less than or equal to the binary code of y. In Figure 3, lattice has six join-irreducible elements. We assigned a binary code of length 6 to each element of the lattice. Habib and Nourine [16] have used binary codes for lattice operations. In the searching problem, if query element has already been compared with join-irreducible elements then it can be compared with other elements using binary code comparisons. For example, a Boolean lattice with elements has join-irreducible elements and this is enough query comparisons; all other comparisons can be done using binary code comparison. Let be a finite lattice. Let be the set of join-irreducible elements of . We consider the set = { ⊥}. The partially ordered set is called the poset generated by join-irreducible elements of . We note that is not necessarily a lattice. In Figure 2 you can see a counterexample. If is a lattice then we can construct a poset generated by the join-irreducible elements of . We can have a sequence of lattices, where is a poset generated by the joinirreducible elements of lattice . We assumed that for all , posets are lattices. If a lattice certifies the just explained property then we call it a matryoshka-lattice. The lattice in Figure 3 is a matryoshka-lattice, but the (left) lattice in Figure 2 is not. It is clear that | | | |. There exists a positive integer such that all elements of the lattice , except the bottom and may be the top elements, are join-irreducible. Let be a first such integer. Then any lattice is the same Tree-like poset Lattice General poset Chain as lattice . Now we have a finite sequence of mutually different lattices . It is clear that { } is a tree-like poset and it has fewer elements than the original lattice L. It is enough to know comparisons between a query element and elements of { }. Therefore we have a more simple search space than in the original one. Using binary codes we can compare a query element with elements of , then with elements of , and so on, finally with elements of . This is the idea of Algorithm 1. Algorithm 1 first constructs the sequence . Then using an efficient search algorithm for a tree, for example the algorithm from [11], a query element is compared with elements of { }. Using binary codes a query element is then compared with elements of the previous lattice, and so on. Finally Algorithm 1 finds comparisons between query element and elements of the original lattice . Algorithm 1 is based on replacement of comparisons of two elements of the lattice with binary code comparisons. We note that comparison of binary codes is insignificant relative to comparison of CGs using graph homomorphism. Algorithm 1: SearchInMat-Lattice(Matryoshka-lattice, query element); Input: Matryoshka-lattice L and query element q; Output: An element of matryoshka-lattice L, which is equal to query element q or "No q in a given matryoshka-lattice L"; 1. 2. ; 3. If has a non-join-irreducible element ( ⊥) then 3.1 Find and numerate all join-irreducible elements of ; 3.2 Assign binary code to each element of ; 3.3 Construct next lattice generated by the join-irreducible elements of ; 3.4 ; Go to 3; 4. Using search algorithm in a tree { } find binary code of query element q; 5. If then else 7; 6. Extend binary code of query element q using binary code comparisons in ; Go to 5; 7. Search for query element q using binary code comparisons in L.
In Figure 3, lattice is generated by the join-irreducible elements of , and lattice is generated by the join-irreducible elements of .
{ } is a tree-like poset. The bold nodes of , , and are join-irreducible elements. A binary code is assigned to each node of and . For any given query element, Algorithm 1 uses only three query comparisons. These are comparisons between a query element and three join-irreducible elements of a tree-like poset { }.

Parallel Search Algorithm
Now we consider a general poset. First we propose a simple sequential search algorithm in a poset, and then using it we suggest a parallel algorithm.

Sequential Search Algorithm
Let be a poset and be any non-empty, finite subset of , | | , where is a positive integer. We call the set as a dataset. We assume that the dataset has both top and bottom elements and that they are different: ⊥. Assume are elements of and and ⊥. Let be an element of : . We call the element a query element. Our search algorithm is based on the following very simple property of posets: Let be elements of some poset. If is FALSE then for any such that , we have that is also FALSE. Figure 3 Algorithm 2 starts from the top element and moves to depth or width for further searching. Algorithm 2 asks a question of the form " ". If the answer is "Yes" then it continues the search in the set of descendants of the selected element (moving to depth). If the answer is "No" then it searches in the complimentary part (moving to width). We note that the ) function returns the -th child of in . Because , the function can be done in constant time since it corresponds to an access to an element of the descendant list D . The Descendant function is a similar. Also we note that the dual algorithm of Algorithm 2 can be easily obtained. It can be used if it is known that the query element is closer to the bottom element.

Parallel Search Algorithm
For parallel computing we use the parallel random-access machine (PRAM) model of computation with processors. In the PRAM model of computation all processors can access common a RAM in a single algorithm-step. In parallel Algorithm 3, the first processor uses Algorithm 2; all other processors use Algorithm 2 with random chosen initial element (step 1.3). Shared information for processors is the Status of an element, which can be ANC (ancestor), NONANC (non-ancestor), and DES (descendant). In Algorithm 3 any query comparison (in steps 1.4, 1.10, and 1.14) will be done once only, that is, two or more processors do not check the same query comparison if they do not come to it at exactly the same time. In other words, there is no overlapping of partition of search space up to query comparisons. The whole algorithm stops when one of the processors returns or the first processor returns "No in ". If the processor , reaches the bottom element, but cannot find a searching element then it chooses a new initial element and searches again. This provides uniform distribution of tasks among the processors.

Conclusions
We analyzed conceptual graph database organizing and managing operations. We proposed a search algorithm for a particular case, when the search space is a special subclass of lattices, so called matryoshka-lattices. In the general case we suggested a parallel search algorithm which is based on simple sequential algorithm. Since the searching in lattices problem is replaced with searching in a tree-like poset with fewer elements than original one we believe that Algorithm 1 is very efficient. However, we do not know how large/small the class of matryoshka-lattices is. There is no easy way to check whether a given lattice is a matryoshka-lattice or not. We remark that the efficiency of Algorithm 3 can be increased by replacing the basic sequential algorithm (Algorithm 2) with a faster one.


extfieldsofstudy:
Biology
Medicine
Computer Science

text:
CytoSaddleSum: a functional enrichment analysis plugin for Cytoscape based on sum-of-weights scores

Summary: CytoSaddleSum provides Cytoscape users with access to the functionality of SaddleSum, a functional enrichment tool based on sum-of-weight scores. It operates by querying SaddleSum locally (using the standalone version) or remotely (through an HTTP request to a web server). The functional enrichment results are shown as a term relationship network, where nodes represent terms and edges show term relationships. Furthermore, query results are written as Cytoscape attributes allowing easy saving, retrieval and integration into network-based data analysis workflows. Availability: www.ncbi.nlm.nih.gov/CBBresearch/Yu/downloads.html The source code is placed in Public Domain. Contact: yyu@ncbi.nlm.nih.gov Supplementary information: Supplementary materials are available at Bioinformatics online.

Overview
Term enrichment analysis facilitates biological interpretation by assigning to experimentally/computationally obtained data annotation associated with terms from controlled vocabularies. This process usually involves obtaining statistical significance for each vocabulary term and using the most significant terms to describe a given set of biological entities, often associated with weights. Many existing enrichment methods require selections of (arbitrary number of) the most significant entities and/or do not account for weights of entities. Others either mandate extensive simulations to obtain statistics or make assumptions about data distribution that need not be justifiable. In addition, most methods have difficulty assigning correct statistical significance to terms with few entities.
Implementing the well-known Lugananni-Rice formula, we have developed a novel approach, called Sad-dleSum, that is free from all these undesirable constraints. It approximates the distribution of sum of weights asymptotically by saddlepoint method to arrive at analytically and computationally tractable form.
We evaluated SaddleSum against several existing methods and demonstrated its ability to adapt equally well to distributions with widely different properties. With entity weights properly taken into account, SaddleSum is internally consistent and stable with respect to the choice of number of most significant entities selected. Making few assumptions on the input data, the proposed method is universal and can thus be applied to areas beyond analysis of microarrays, such as deep sequencing, quantitative proteomics and in silico network simulations. SaddleSum also provides a term-size dependent score distribution function that gives rise to accurate statistical significance even for terms with few entities. As a consequence, SaddleSum enables researchers to place confidence in its significance assignments to small terms that are often biologically most specific.

Enrichment Statistics of Sum-of-weights Scores
Suppose that you have obtained some measurements for a number of genes or proteins in an organism. These can be gene expression log-ratios or values computed through some simulation. The problem now is to biologically interpret your experiment, that is, to link it to known terms and concepts.
One way to do so is to obtain a controlled vocabulary that covers the domain of your investigation and serves as basis for annotation of the genes from your organism. This means that every term in that vocabulary is associated with one or more genes; the term describes its associated genes. Your original problem is now transformed to the question of finding what terms best describe your overall measurements.
Let us further assume that gene measurements, which we will call weights, indicate relative importance of genes. If that is not so, for example if all highly expressed genes should be treated equally, you can transform your values so that this assumption holds and continue from there. A natural way to express the importance of each vocabulary term is to compute its score as the sum of weights of all genes mapping to that term.
Unfortunately, the score just calculated is not a good way to compare terms. Different terms may contain different numbers of genes and hence cover different parts of your measurement set. Thus, it may be possible that difference in scores of two terms is only due to their coverage. Normalizing by the number of genes may help but does not go far enough; there is still a question of the scale of the scores and their distribution.
The standard approach to this issue is statistical: we want to know the probability of a given score occurring by chance with respect to some null distribution. This probability is known as P-value and can be used as the statistical significance of the term. Note that there is a null distribution here associated with each term.
In our case, it is reasonable to assume that the scores are built by summing m independently and identically distributed weights, where m is the number of genes mapping to the term. If the term P-value is sufficiently small, say 0.01, we can conclude that it is very unlikely that term score has arisen by chance. Therefore, we are able to interpret our dataset using that term.
SaddleSum is a tool that automates the above procedure. It requires a term database and a collection of gene labels associated with weights. It outputs the most statistically significant terms together with their estimated statistical significance. To compute P-values, SaddleSum first estimates the distribution of weights using all the supplied weights. Then using this estimated distribution, it approximates the P-value of a score using the asymptotic saddlepoint approach developed by Lugananni and Rice. This estimate is extremely accurate, even for terms with very small number of associated genes or for very small P-values.
To correct for the fact that a term database usually has many terms that enhance the chance of random matches, it is necessary to perform multiple hypothesis testing correction. SaddleSum uses Bonferroni correction for multiple hypothesis testing, where raw term P-values are multiplied with the effective database size to give E-values. We define the effective database size as the number of terms in the term database that map to at least k genes corresponding to selected nodes, where k is the minimum term size. This parameter is calculated at the time of the query. By default, the calculated value is used to compute E-values but you can can override it by changing the corresponding form entry. For example, raw P-values can be displayed by setting the effective database size to 1.

SaddleSum software
SaddleSum can be used through three interfaces: command line (standalone version), web and as a Cytoscape (http://www.cytoscape.org/) plugin.
The standalone version is written completely in the C programming language and has no dependencies beyond the gcc compiler and GNU make (although it is likely that it can be adapted to compile using other development tools). It provides a command line interface and uses term databases in a simple tab-delimited format (GMT) as well as in SaddleSum's own ETD (Extended Term Database) format.
The web version provides a wrapper for the standalone version via a web form. The server script that interacts with the standalone version is written in Python programming language and is a part of qmbpmntools package, which also includes ITM Probe, a framework for analysis of information flow in interaction networks based on random walks. The qmbpmn-tools package depends on a number of external Python libraries and on the Graphviz suite for visualizing graphs.
Cytoscape is an open source platform for complex network analysis and visualization written in Java programming language. Apart for a rich set of graph visualization tools, it provides an interface for externally written plugins that provide additional functionality such as network analysis algorithms, database import and functional enrichment analysis. Cytoscape users are therefore able to combine algorithms and data from different sources to perform complex network-based analyses.
CytoSaddleSum is a Cytoscape plugin that enables SaddleSum queries from Cytoscape platforms. It can interact either with a locally installed command-line program directly, or through our web server. The results are presented as a Cytoscape network view showing term relationships. Term statistics, written to node attributes in the relationship network, can be manipulated by the user.

Standalone Program
The standalone version of SaddleSum is written in the C programming language and requires no additional libraries. It offers a standard UNIX command line interface and allows users to specify multiple term databases in the GMT format used by GSEA as well as in SaddleSum's own ETD (Extended Term Database) format (see Structure of Extended Term Databases (page 11) below).

Downloading
The source code for the standalone SaddleSum is available from the NCBI FTP site (ftp://ftp.ncbi.nih.gov/pub/qmbpmn/SaddleSum/src) as a tar.gz archive. Releases of SaddleSum share the version numbering with the corresponding qmbpmn-tools.

Building and installing executables
After downloading a source code, extract it to a chosen directory and enter the saddlesum-<version> directory. The standard process of: ./configure make make install should install the binaries into your executable directory. To clean the build, type make clean. This requires gcc and GNU make.
We have successfully built the source on Linux systems, Mac OS X with gcc and on Windows XP using MinGW. It may be possible to build it on other platforms but we have not attempted to do so.

Obtaining Term Datasets
Term datasets corresponding to the three Gene Ontology (GO) categories and KEGG pathways are available for a number of species in both ETD and GMT format (gzipped). ETD datasets are recommended but GMT versions of the same data is provided for compatibility with the earlier version. The FTP link is ftp://ftp.ncbi.nih.gov/pub/qmbpmn/SaddleSum/term_datasets . The most recently built datasets are available under in the current subdirectory.
The naming of the GMT files follows the convention: The <database> field is either GO-<category> or KEGG, where category is one of mf (molecular function), bp (biological process) or cc (cellular component For example GO-bp-pfa.gmt.gz contains the GO biological process database for Plasmodium falciparum. Each ETD file contains all provided term datasets for a single species (the three GO namespaces plus KEGG). The naming of the ETD files follows the convention: <species>.etd.gz The species field again uses the KEGG three letter codes shown above.

Using SaddleSum
Standalone SaddleSum has a simple command line interface: For full list of options, type: saddlesum -h or see the saddlesum (page 7) page in this manual.
The <weights_file> argument can either be a filename path or -, which means that the weights are to be taken from the command line. The weights are supplied in the two-column tab-delimited format, where the first column gives entity (gene) IDs, while the second gives their weights as floating point numbers. No comment lines or multiple columns are allowed.
Entity IDs depend on the term database being searched. Each ETD database contains, in addition to the term datasets, an abbreviated version of the NCBI Gene database for its species. Thus, when using an ETD database, SaddleSum is able to interpret entity IDs provided as Gene IDs, as gene symbols and as gene aliases. If provided symbol is ambiguous, SaddleSum reports a warning or an error, depending on whether the ambiguity can be resolved.
The GMT term databases supplied on our FTP site use NCBI Gene IDs to label genes and hence the weights supplied to saddlesum program must also use NCBI Gene IDs to supply weights. We have decided on using NCBI Gene IDs for this purpose because many genes have several widely-used names, while GMT format does not allow specifying aliases.
The database arguments are in the format <namespace>:<term_db> where <namespace> is an arbitrary namespace label and <term_db> is the path to the term database. The first database can be specified without the <namespace> label, which indicates that the <term_db> is an ETD file. If <namespace> is present, a GMT dataset is assumed. All subsequent arguments must specify the namespace part and the term datasets must be in GMT format. In this way, it is possible to combine an ETD database with several GMT ones. The recommended use for GMT databases is to create customized databases containing associations that cannot be found in GO or KEGG.
Namespace labels for GMT databases can be repeated. Significant terms under the same namespace are sorted and printed together, with each results table headed by the <namespace> label. Term datasets within an ETD database already contain their namespace labels, which can be inspected using the saddlesum-show-etd (page 10) utility.

Examples
The One can also experiment with options, such as setting the cutoffs and similar. Note that the down-regulated weights were obtained by flipping the sign on the original log2 ratios and setting all weights smaller than zero to zero (please see our paper for the explanation).

Manpages saddlesum SYNOPSIS
The standalone saddlesum interface takes the following general form:

Arguments <weights_file>
Tab-delimited file with entity ids and weights. If <weights_file> is specified as -, use standard input.

<namespace>:<term_db>
The text up to the first column denotes the namespace label while the rest of the argument denotes a path to a term database. For the first database, the namespace component can be omitted, in which case the file is assumed to be in ETD format. All subsequent databases should be in GMT format and have namespace specified. This allows combining multiple databases to obtain joint results. Significant terms for each namespace are treated separately.
Generic options -h Print a description of all command line options.

-V
Print the version number and exit. The version number always matches that of the qmbpmn-tools.

Statistical options -m <min_term_size>
Set the minimum number of entities for a term to be considered (default = 2). Only entities with supplied weights count towards the term size.

-e <Evalue_cutoff>
Set the largest E-value for a term to be considered significant (default = 1e-02).
Note: Since saddlesum uses an algorithm that quickly rejects those terms that cannot have an E-value smaller than <Evalue_cutoff>, the choice of <Evalue_cutoff> can significantly affect the running time of the program.
-n <effective_db_size> Set the effective term database size for applying Bonferroni correction (i.e. calculating E-values) to P-values output by the algorithm (default = the total number of terms considered). Setting <effective_db_size> to 1.0 will result in the original P-values being returned.
-s <statistics_type> Set statistical method used to evaluate P-values. The argument must be one of the following: wsum (default) use SaddleSum statistics based on sum-of-weights score for each term hgem use one-sided Fisher's Exact test.
Note: Option -s hgem implies option -d (whether specified or not). Also, one of -r or -w options must be used to specify the cutoff for selecting weights.
-a When this option is specified, all weights that can be mapped to valid entities are used as statistical background. Otherwise, only those weights that both map to a valid entity and a vocabulary term in the term database are used.

-x <namespace>
Exclude <namespace> from ETD database. Each ETD database may contain multiple namespaces.
This option allows specific namespaces to be totally excluded from consideration. It affects the effective database and hence the term E-values. More than one namespace can be excluded by using this option multiple times.
Note: Use saddlesum-show-etd program to discover the names of all namespaces present in an ETD file.
-T <term_id> Compute statistics only for the term with ID <term_id> and display the list of entities associated with that term, together with their weights. All other statistical and weight processing options can be specified in conjunction with -T but -e has no effect.
Note: If specifying -m results in the term to be excluded from computation of P-value, no statistics will be computed and displayed.
Weight processing options -t <weight_transformation> Apply a transformation to each of the provided weights prior to other applying other processing options (see below) and calculating enrichment statistics. The argument must be one of the following: flip flip the sign of each weight abs take the absolute value of each weight.
When this option is omitted, no transformation will be performed.

-r <rank_cutoff>
Set all weights ranked lower than <rank_cutoff> to 0. If there are several weights tied at <rank_cutoff>, keep all of them.
Note: Only one of the -r and -w options can be set at the same time.
-d Discretize weights. Set all weights greater than 0 to 1 and all those smaller than 0 to 0.
Note: The weight processing options are applied in this order: -t, then -r or -w and finally -d.

Output options -O <output_file>
Output results to <output_file> instead of to the standard output.

-F <output_format>
Select output format. The argument must be one of the following: txt (default) print results as formatted (pretty) text.
tab print results as a tab-delimited file. Different sections are separated by heading lines starting with # character.
-W Print warnings about entity identifiers from the <weights_file>.
-U Print ids from <weights_file> that are not present in the term databases.
Note: Options -W and -U apply only to text output. Tab-delimited output always contains sections containing warnings and unknown ids.

Arguments <term_db>
A database in ETD format.

Generic options -h
Print a description of all command line options.

-V
Print the version number and exit. The version number always matches that of the qmbpmn-tools.

Output options -N
Only list the namespaces present in the database, one per line. Otherwise, a more detailed info table is output.
Note: Specify -Ftab to obtain only the list of namespaces, without any other text.

-O <output_file>
Output results to <output_file> instead of to the standard output.
-F <output_format> Select output format. The argument must be one of the following: txt (default) print results as formatted (pretty) text.
tab print results as a tab-delimited file. Different sections are separated by heading lines starting with # character.

Structure of Extended Term Databases
Extended Term Databases (ETDs) are binary files that contain term databases used by SaddleSum. They are created through Python scripts from qmbpmn-tools. Here, we describe the structure of the binary format.
Each ETD consists of a header, genes database and one or more namespaces. The header contains the overall information about the database. Genes database is derived from NCBI Gene and serves to enable parsing of gene label aliases. Each namespace is a separate term database, containing terms, their relationships and mapping to genes.
Note: In the listing that follow we use C-like pseudocode to indicate the types of the fields. These resemble C declarations with a difference that array sizes are usually not fixed but need to be read from the file. The type uint32 here means 32-bit little-endian integer.

Header
The header part is written as following (comments are on the right):

Genes Database
The genes database is derived from NCBI Gene records for a given species. It contains a list of genes, their descriptions, their symbols and lists of conflicts. There are two types of conflicts. Type 1 conflict occurs when the canonical gene symbol for a gene is an alias of another gene. These are always resolved to mean the gene that has the conflicting label as the canonical symbol. Type 2 conflict occurs when a label is an alias of multiple genes but is not set as a canonical symbol for any gene. Such conflicts cannot be resolved. The genes database structure is:

Term Namespaces
Each namespace is a separate term database. It contains terms (IDs and descriptions) their relationships and maps to genes. KEGG and Gene Ontology databases differ according to their metadata. The structure is: KEGG namespaces use three items in metadata field: organism prefix, leaf URL format (URL format for the page describing a leaf term) and higher URL format (URL format for terms higher in the hierarchy). Gene Ontology namespaces have a single item; a url format for Amigo website. All URL formats must contain a single %s formatting specifier.

Web Service
SaddleSum web service (http://www.ncbi.nlm.nih.gov/CBBresearch/Yu/mn/enrich/) allows users to input their gene weights through a web form and receive results as HTML pages. The user interface consists of the input form, the output page and the term details page.
Note: SaddleSum web service runs standalone executable on the server and hence many of its options directly correspond to the command line options described on the man page for the saddlesum (page 7) program available as an Appendix. We will here concentrate mostly on the aspects unique to the web service.

Input Form
Use the input form to set up SaddleSum queries. It consists of four sections: term database and weights, statistical parameters, weight processing parameters and output parameters.
The only mandatory parameters are located in the Term Database and Weights section. You must choose an appropriate database from the dropdown box and enter gene labels with their weights. Since all databases that can be selected are in ETD format (see Obtaining Term Datasets (page 5)), you may enter gene labels as NCBI Gene IDs, as canonical gene names or as aliases. There are two ways to enter weights: through the text box or by uploading a text file. The format is the same in both cases: it consists of several lines where each line should contain a gene label string, followed by spaces or a TAB, followed by a floating point weight value.
The Statistical Parameters determine which database terms are retrieved as significant. These are E-value cutoff, minimum term size, effective database size and statistical method. See Enrichment Statistics of Sumof-weights Scores (page 3) for an explanation of SaddleSum statistics and the saddlesum (page 7) man page for the detailed description of these options. Note that apart from the default Lugannani-Rice statistics, it is also possible to select One-sided Fisher's Exact test statistics, which are based on the hypergeometric distribution. In that case, you must select a cutoff under the weight processing parameters.
The Weight Processing Parameters can be used to easily perform the most common transformations of weights and set weight cutoffs. Again, the saddlesum (page 7) man page contains all the details about the allowed values.
The look of the SaddleSum output is controlled through the Output Parameters section. You can select the output format (HTML, text or tab), the format of the term relationships graph image (see below) and its color scheme. If you choose text or tab as output format, SaddleSum will not produce a term relationship graph.
To run SaddleSum press the QUERY button.

Output Page
To display query results SaddleSum produces an output page showing an image of the term relationships network, the tables listing significant terms, and a query and database summary.

Term relationships network
is placed at the top of the results. It contains terms as nodes linked by their relationships supplied by the term database they belong to. Of the databases currently by the web service, Gene Ontology has term relationships as a directed acyclic graph, while KEGG has a tree hierarchy. Only the significant terms according to the E-value cutoff plus their hierarchical parents are shown. Term significance (log E-value) is indicated by node colors. Clicking a term node opens a new window or tab in the browser that show the full description of the corresponding term.

Significant terms
are listed in the tables below the term graph. Each namespace with significant terms has its own table. A namespace table shows for each significant term its database identifier, description, the number of associations with genes, score and E-value.
Clicking on term identifier opens a new window or tab in the browser showing the full term description, while clicking on the last three columns brings up a statistical summary of the term and a full list of all genes associated with it together with their weights.

Query and database summary
is placed at the bottom of the results page. It echoes most of the input parameters, such as the name of the selected database, statistical parameters and weight transformation. In addition, it shows the statistics collected during the execution of the query that depend on the actual submitted gene identifiers and weights. These include the numbers of submitted and valid gene identifiers, total and used terms, and unused gene identifiers. Finally, you can toggle a list of unrecognized identifiers, if there were any.

Examples
The page http://www.ncbi.nlm.nih.gov/CBBresearch/Yu/mn/enrich/examples.html contains links to three examples of collections of weights that could be used with SaddleSum. The links lead to SaddleSum query forms filled with the log2 ratios of gene expressions, taken from selected microarrays from the NCBI GEO database (http://www.ncbi.nlm.nih.gov/gds). These are the same weights available as examples for the command-line version (Examples (page 7)). Once you reach the query forms for an example, you only need to press the QUERY button to run it and obtain the results.

Cytoscape Plugin
CytoSaddleSum is a Cytoscape plugin that provides interface to SaddleSum functionality. It works by querying SaddleSum either locally (using the standalone version) or remotely, through an HTTP request to a web server. The results of a functional enrichment query are shown as a term relationship network, where nodes represent terms linked by edges showing term relationships. The statistics and other query details for each term are written as node attributes. This allows easy integration of SaddleSum into a network-based data analysis workflow.
CytoSaddleSum was developed for Cytoscape version 2.8. All the source code written a the NCBI is released into public domain.

Downloading and Installing
It is possible to download CytoSaddleSum either as a JAR file ready for installation as a Cytoscape plugin or as zipped source code archive. Both can be found on the NCBI FTP site (ftp://ftp.ncbi.nih.gov/pub/qmbpmn/CytoSaddleSum/). Releases of CytoSaddleSum share version numbers with other SaddleSum interfaces, starting with 1.4.
To install CytoSaddleSum, copy the JAR file you have downloaded to the plugins subdirectory of your Cytoscape distribution. If the installation location was correct, you would see the SaddleSum entry in the Cytoscape Plugins menu.

Building from Source
The source code was mostly developed using NetBeans (http://www.netbeans.org/) and built using Apache Ant (http://ant.apache.org/). To build the JAR file, you first need to unzip the source distribution file, put cytoscape.jar onto your CLASSPATH and copy the file build.xml.git in the root of the distribution to build.xml. Then type: ant package to build the JAR named CytoSaddleSum.jar in the root distribution directory.

Starting plugin from Cytoscape
Start CytoSaddleSum by choosing the Cytoscape menu entry Plugins → CytoSaddleSum → Query Form.
After reading the configuration file (see below), CytoSaddleSum attempts to retrieve the list of available term databases that can be selected for a query. After that, it creates a query form and inserts it into the Cytoscape Control Panel (on the left of the Cytoscape window). You may need to resize the Control Panel to see the entire SaddleSum query form.
The query form has a look and functionality similar to the query form of SaddleSum web interface. Three action buttons can be found at its bottom: • QUERY -to start running a SaddleSum query (see Setting up a query (page 21)); • RESET -to reset the form; • CONFIG -to change CytoSaddleSum configuration (see Configuration (page 20)).
• LOAD -to load CytoSaddleSum results saved as attributes in a term relationship graph (see Saving and restoring results (page 24)).

Configuration
Configuration of CytoSaddleSum is handled though a separate dialog.
There are two possible configurations: Web Query This option will configure CytoSaddleSum to query the SaddleSum web service over HTTP.
Choosing this method means that you are not required to download, compile or configure the command-line version of SaddleSum. You may notice some latency when starting and running Cy-toSaddleSum and you will not be able to use custom GMT formatted term databases.
Local Query This option will configure CytoSaddleSum to run a local program. Choosing this method means that you need to download and compile the command-line version of SaddleSum. Queries will be generally faster and it will be possible to use custom GMT databases as well as ETD databases downloaded from the SaddleSum FTP site.

Configuring for web queries
Configuring CytoSaddleSum to perform a web query requires clicking the "Web query" radio button and entering the URL for the SaddleSum web services into the "Web query URL" box.
Note: When creating the initial configuration, CytoSaddleSum will automatically set the URL of the default SaddleSum web service in the "Web query URL" box and this need not to be changed unless the server address changes.

Configuring for local queries
Configuring CytoSaddleSum to perform a local query requires more work than configuring it to perform a web query. First, you need to download, compile and install the standalone SaddleSum (see Standalone Program (page 5)) and, optionally, some ETD databases that you may use. In the configuration dialog you need to click the "Local query" radio button and set the paths for: • The SaddleSum binary (for example /usr/local/bin/saddlesum) • The directory holding downloaded ETD files.

Note:
CytoSaddleSum assumes that the second binary from the standalone package (saddlesum-show-etd) can be located in the same directory as saddlesum.
Note: Downloading ETD files is optional but if none are present in the specified directory, only local queries using custom GMT term databases will be enabled.

Setting up a query
CytoSaddleSum operates on the currently selected Cytoscape network. Before running a query, you need to have a network with at least one floating point node attribute that can serve as node weight. The alwayspresent canonicalName attribute provides node identifiers for the query, while the weight attribute can be selected through a dropdown box on the query form. Select all the nodes in the network that you wish to be used for the query (see Warning below).
After selecting the network and the nodes within it, select an appropriate term database for your query. This may be a species-specific ETD database from the dropdown list (containing Gene Ontology and KEGG pathways) or a custom database in GMT format. GMT format, used by the GSEA tool is described at http://www.broadinstitute.org/cancer/software/gsea/wiki/index.php/Data_formats Next, choose statistical and weight processing parameters for the query. We recommend using the default values. Short description of each parameter is available through tooltips, while full descriptions can be found on the man page for the command-line saddlesum program.
For queries using the default Lugannani-Rice statistics with sum-of-weights score, the weights may take any floating-point value: the score for a term is the sum of the weights for each node mapping to it. The other option for statistics is One-sided Fisher's Exact test or equivalently, hypergeometric distribution. This gives the statistics reported by most other functional enrichment tools. In order to use these statistics, you have to select a cutoff, either By Rank (e.g. select nodes with top 50 weights) or By weight (e.g. select all nodes with weight greater than 0.05). The value of the cutoff parameter (rank (e.g. 50) or weight (e.g. 0.05) should be entered in the "Cutoff Value" box.
Warning: Selection of nodes has different meaning in CytoSaddleSum than in some other enrichment tools available in Cytoscape. Here, the node selection effectively determines the statistical background for the enrichment query. All selected nodes are considered, even those without a value for the weight attribute. Such nodes are given the weight of 0. The "significant" nodes for the purpose of the Fisher's exact test are chosen using the cutoff parameters. This means that some nodes not of interest can be totally excluded from the enrichment analysis.
To start a query, press the QUERY button. A progress dialog will appear and, after a while, the query results (or an error message) will be shown.

Working with the results
For each query, CytoSaddleSum results consist of a term relationship graph and a set of tables inserted into the Cytoscape "Results Panel" (located on the right of the Cytoscape main window when docked). To distinguish different queries, each query has a distinct name consisting of the prefix SSUM followed by a three-digit number (for example SSUM019). This number is incremented every time a query is run up to 999 and then reset to 0.
Note: The summary tables and the term relationship graph for a query are linked. Destroying a term relationship graph will also remove the corresponding summary tables from the Results Panel.

Summary tables
At the completion of each query a new tab (labeled with the query name described above) is embedded into Results Panel. This tab contains four tabs titled "Results", "Summary", "Warnings" and "Unknown IDs".
The Results tab contains tables of significant terms found by SaddleSum, separated by namespace (e.g. Biological Process, KEGG Pathway ...). Each row shows term ID, term description, total number of entities (genes) associated with that term, term score (sum of the weights of entities mapped to that term) and Evalue (statistical significance; expected number of terms that would score no worse than that term under null model). If there are no results, the Results tab will be empty and titled "No Results".
The Summary tab contains the query and database summary, including statistics on database size, number of submitted weights and similar. The Warnings and Unknown IDs tabs show information about the node IDs that were either not recognized within the term database (Unknown IDs) or were recognized as potential conflicts (Warnings). A conflict occurs when the submitted node ID could be interpreted as an alias to more than one entity (gene) within the database. Most conflicts can be resolved as one name takes precedence over others but in some instances the labeling is totally ambiguous.

Term relationship network
The term relationship network shows graphically the significant database terms retrieved by the query and the relationships between them. Major term databases such as Gene Ontology and KEGG are do not only consist of mappings of genes to terms, but also contain hierarchical relationships between them. The Sad-dleSum ETD format databases contain such relationships and thus SaddleSum is able to display a graph of significant terms, as well as their list.
Each term relationship network consists of terms as nodes and their relationships as directed links. Each node is associated with Cytoscape node attributes corresponding to result table columns. Results from ETD databases contain not only the significant terms as nodes, but also the terms higher in the hierarchy, up to the root of the hierarchy. These non-significant terms do not have all attributes set. GMT databases do not contain relationships between terms and hence the resulting term network contains only nodes without any links. The term network is empty is SaddleSum query produces no results.
CytoSaddleSum applies a custom visual style to term relationship networks. Term IDs serve as node labels, while term descriptions serve as tooltips. Statistical significance (E-value) for each node is indicated by color, with significance increasing from light to dark blue. The color scheme is discretized based on the logarithm of E-value and the colors belong to the Blues8 series of Brewer Colors (see Acknowledgments (page 27)).
Built-in Cytoscape plugins and utilities allow easy access to additional resources related to terms. For example, to browse a detailed description of a Gene Ontology term, right-click a node in a term relationship network. In the popup menu that appears chose LinkOut → Ontology → Gene Ontology (Quick GO by ID). A full description of the term will appear in your web browser. For KEGG pathways terms (lowest in the hierarchy), use LinkOut → KEGG → All Species (Use KEGG ID).

Selecting nodes mapped to significant terms
Double clicking on a row in a namespace table in the "Results" tab will select the corresponding term node in the term relationship graph. If the original graph used for the query is present, it will be placed in focus and all the nodes mapped to that term will be selected. You can then easily examine the weights and other attributes of these nodes through Data Panel.

Saving and restoring results
Each CytoSaddleSum query stores its results by setting node and network attributes in the term relationship graph. This network and its attributes can be saved through Cytoscape and then be reloaded in a different session. To restore the corresponding results panel, select a term relationship network and hit the "LOAD" button on the query form.
Note: The "LOAD" button will be enabled only if the selected network contains saved results and these results are not already shown in Results Panel.
Warning: Since all SaddleSum results are placed into node and network attributes, it is possible to arbitrarily edit them and change them. This can cause unpredictable effects to the functioning of Cy-toSaddleSum. Make sure you have the original results saved before any editing so you can restore them if problems occur.

Exporting results to text files
The results stored in a term relationship network can be exported to text files though the Export menu. Use File → Export → SaddleSum Results as TXT File... to export in plain text format or File → Export → SaddleSum Results as TAB File... to export in tab-delimited format. The result formats are identical to the ones used by the standalone saddlesum (page 7) program. The text format is human-readable but does not contain the information necessary to generate the term relationship network. The tab-delimited format may not be as easy to read but contains the entire set of results, including the nodes and edges of the term relationship network.

Importing results from TAB files
The TAB files produced by the standalone saddlesum (page 7) program or through Export functionality can be used directly to recreate the term relationship network and the results panel in Cytoscape. Use the menu item File → Import → Import SaddleSum Results from TAB File... to select and load the results. A term relationship network will appear, together with a corresponding results panel. CytoSaddleSum will assign a new label to the term relationship network and the results panel, as if the results originated from a direct SaddleSum query.
Note: The results loaded in this way will not be connected to any "original" graph. Hence, you will not be able to select the nodes mapped to terms by clicking on the rows in the namespace table of the panel corresponding to the imported results.

Troubleshooting missing results
Sometimes a query produces no significant results without apparent cause. This list may help in that case: 1. Check that a database for the appropriate species is selected. An indicator for this problem would be too many Unknown IDs.
2. Ensure that node labels correspond to database gene labels. ETD databases contain list of aliases for each gene and hence are able to interpret non-canonical node IDs. To use GMT databases, your node IDs must correspond to those used by term mappings.
3. Ensure that the correct network and the correct weight attribute is selected when pressing the QUERY button.
4. Check if all important nodes within the network are selected -only the weights of selected nodes will be considered.

5.
Check that E-value cutoff is sensible. Sometimes it is necessary to enter a larger cutoff (such as 1 or even 10) for some terms to appear in results.
6. Ensure that you have selected a cutoff when using One-sided Fisher's Exact test statistics.
7. Check other input parameters as they may significantly influence results as well -use defaults if unsure.


s2fieldsofstudy:
Computer Science
Business

text:
Design and Implementation of the Logistics Management System Based on J2EE Technology

The J2EE model is the use of advanced software layered design ideas to support framework-based development, and it can reduce development effort and cost, while reducing the degree of coupling of components, and greatly enhance software maintainability, scalability to meet the large-scale management information system requirements. The paper proposes the design and implementation of the logistics management system based on J2EE technology. This article describes the basic functions of logistics management system based on J2EE technology design, the overall structure and implementation of key technologies involved in the system.

Introduction
As global economic integration, China has gradually become the world's manufacturing and procurement centers, logistics increasingly important role in them. In order to meet the needs of modern economic development, logistics enterprises to information technology, integrated, professional change, fully integrated logistics and information technology, the establishment of a logistics management system based on modern management information network architecture.
Namely Java 2 Enterprise Edition J2EE, Sun has introduced a multi-layered structure of the distributed application model, the model has the ability of reusable components, based on the Extensible Markup Language (XML) data exchange, a unified security model, and flexible transaction control, it set up with scalability, flexibility, ease of maintenance of enterprise information systems to provide a good mechanism, has incomparable advantages compared with traditional Internet application model [1]. Developers can not only quickly new problem domain solutions, and its platform-independent, component-based J2EE solution is no longer subject to the restrictions of providers of products and application programming interface. J2EE architecture, the presentation logic, business logic and data logic, phase separation, and the use of advanced software layered design ideas, support based on framework development, reduce development effort and cost, while reducing the degree of coupling of components, greatly enhancing software maintainability, scalability, and to meet the requirements of large-scale management information system.
With the rapid development of the current socio-economic, manufacturing, commerce, and the size of the business continued to expand, products, raw materials, a large demand, the amount of logistics is also increasing. Therefore, the demand for third-party logistics services is virtually gone up. To further enhance the efficiency of modern logistics management, logistics management must have a thorough improvement. In fact, whether at home or abroad, logistics management information integration model has long been widely recognized and has been widely applied. However, specifically how to do to make the information system and management structure is not out of line and keep up with the pace of upgrading it? This is an urgent need for more in-depth study of the modern enterprise logistics management information system, in order to allow enterprises to achieve sustainable development goals at the same time, as much as possible to maximize the quality services to customers; the same time, in the service process, but also seek to reduce logistics costs, reducing costs, and ultimately achieve the purpose of profit.
With the development of J2EE gradually evolved into component-based, modular components, the center of gravity of the developer from learning techniques to familiar with business, business infrastructure platform that can help to achieve and to build fast and flexible business systems. Engaged in the root of customer needs-based, starting from the fundamental task of the software development, to find and use some kind of description of the business method, so this method can adapt to various changes in the business infrastructure platform. For many years engaged in enterprise management information system, application, in-depth understanding of customer needs, summed up the industry business model, and workflow system, rights management systems, reporting and management system based on J2EE technology accumulation re-designed and realized based on J2EEtechnology business infrastructure platform. The paper proposes the design and implementation of the logistics management system based on J2EE technology.

Logistics management information system functions model
Enterprise management information system, logistics management information system is very important to a subsystem [2]. The main role of the logistics management information system is the logistics system and beyond all the information collection, storage and processing, and extract an effective logistics management information, and then various forms of output. Under normal circumstances, the common form of logistics management information systems: forms, documents, graphics and reports. These outputs form is usually determined based on output, managers and leaders can be a reasonable overall planning of logistics activities based on this information correct and effective organization of work, and then the logistics activities, coordination and control of the normal operating subsystem run, this will reduce the material loss of power, easy to greatly improve the management efficiency of the logistics work. For logistics management and other enterprise management, operational decisions will be more scientific. Logistics management information system to work, product ordering, purchasing, inventory, shipping and distribution, information management and deployment, you can aim at the timely and accurate, but also of the communication base and network of communication lines, and to protect the modernization of the communication means in order to improve the efficiency of logistics operating system. On the logistics enterprises, the basic logistics activities including transportation, storage, handling, packaging, distribution, processing, logistics management information system also runs through this activity.
Customer management subsystem: customer data collection, classification, archiving, retrieval and management, comprehensive grasp of different customer groups, the nature of the customer, customer demand, customer credit programs, prices, markets, information and other information to provide customers with a variety of services, timely and properly resolve the various problems encountered by customers in cooperation [3]. The subsystem includes a customer login management, customer data management, customer inquiries and other functions, as is shown by equation1.
Treasury management process, in order to carry out the reservoir area and the library full range of effective management, it is necessary to achieve the logistics management information network. Otherwise, a library, and storage all by hand, not only the efficiency will be greatly reduced, but also for the staff, because of their workload is very large, tend to do a lot of wasted effort, and thus give rise to twice the power semi-adverse situation.
Order Management subsystem: the order is a basis for settlement of logistics operations and costs, through standardization, modularity and process orders, a reasonable allocation of the implementation details of the logistics services and charges, and as a basis, the allocation of appropriate resources monitor the implementation of the results and accounting costs incurred, and the parties in the implementation of the orders be evaluated to obtain the information of customers, costs, funding, delivery of customer service and business sectors as a reference. The subsystem consists of the order reception / entry, order inquiries, order tracking and other functions, as is shown by equation2.
Speaking from a different angle from vertical management point of view, can the work of the entire logistics enterprise is divided into operating layer, control layer and the management at three levels. Logistics management information of these three levels must also be involved everywhere, exhaustive [4]. Conversely, if the course of business of the three levels of bad problems, then mop-up will adversely affect the overall operation of the logistics enterprises, as is shown by figure1.

Figure. 1 Logistics management system example
The storage management subsystem: warehouse management, including storage resource management and business processes to achieve, you can achieve a multi-polar management of the Treasury, operating motion segmentation and scheduling strategies, stock management, and inventory of a variety of strategies [5]. Including receiving, quality inspection, put away, picking, distribution processing, shipping, replenishment, inventory control, visualization, monitoring, transfer database, inventory and other functions, as is shown by equation3.
Supplier management, according to the history of dealings with suppliers, suppliers, qualification management, and regularly update the product catalog of supplier, seamless integration with the contract module, query the information of the contract signed with the supplier and performance of the contract.

Design and implementation of the logistics management system based on J2EE technology
Design and implementation of logistics management system based on J2EE business infrastructure platform, the J2EE business infrastructure platform has been successfully applied to the design and development of multiple systems, and applied to the human resources management system, customer service systems, decision support system software has the following characteristics: based on open architecture, based on the MVC structure designed to achieve the separation of business and data. Advanced architecture and design ideas, different people develop different business modules. System with easy to maintain, adapt to a variety of heterogeneous and interoperability. Business functions with the improvement of market structure, mode, and operating rules may at any time to expand and upgrade.
Hibernate is an excellent open-source ORM (Object Relational Mapping) framework, which provides a powerful, high performance object to relational database persistence services. Hibernate, Java programmers can use object-oriented programming thinking to manipulate the database, Advanced Engineering Forum Vols. 6-7 381 significantly reducing the time of hand-coding operations, JDBC and SQL [6]. In addition, Hibernate supports almost all major commercial databases and open source database, and supports a variety of caching mechanism, through a simple configuration, the user can use the services of third-party cache, greatly improving the efficiency of the operation of the system database. The data persistence layer using is Hibernate + DAO pattern of development. This architecture, each layer is only dependent on its layer below, for example, changes to the database without modifying the presentation layer; something unique in each layer to other layers hidden, so to ensure the application to modify them easy to modify not cascade to other layers. This multi-tier architecture is particularly important in the enterprise-class system, it ensures a clear division of responsibilities, with greater scalability and flexibility is defined as equation 4.
Servlet is a server-side Java program is built on the cornerstone of Web-based application, is essentially a small, platform-independent Java classes, with the characteristics of cross-server platform. The servlet receives the request object from the extracted parameters to handle the business logic, and ultimately respond.
JSP (Java Server Pages) is initiated by Sun, a number of companies participate in the development of a powerful dynamic web technology standards. JSP provides a unique development environment for creating highly dynamic Web applications. A JSP Java as its scripting language, to join the Java program fragment and JSP tag in the HTML file, JSP has all the advantages of the Java language, including security, cross-platform; JSP technology page design and business logic separation to distinguish between the role of Web designers and Web developers. In the presentation layer of the system, and ultimately to the client's view is generated by JSP, the JSP and custom tag library extension, as is shown by equation5.
, ( (5) XML (extensible Markup Language, Extensible Markup Language) is a content-oriented markup language created by the W3C. Because it has a more semantic, good scalability and easy to use, self-describing characteristics particularly suitable for semi-structured data on the Web, it can be used for data exchange [7]. The implementation of this system, the server required standard JAVA deployment descriptor, the data persistence layer of the Hibernate configuration file, and use XML mapping document and the system required some configuration.
J2EE is to develop scalable, ideal load balancing, multi-tier distributed cross-platform enterprise application platform. The heart of J2EE is a set of norms and guidelines for the definition of a standard platform for developing multi-tier distributed enterprise applications using the Java language, J2EE effectively meet the deepening needs of industry information. XML technology, XML is a meta-markup language, in the construction of information systems as a data carrier and medium of exchange, to maintain the openness and ease of integration of the system data.
Open source frameworks (eg Struts, Log4j, etc.) as the information system of the Web framework, the framework is based on J2EE and enterprise-level Web application framework comply with MVC2, its core is to achieve loose coupling of multi-tier application for the business group, the platform laid a good foundation. Web framework used in the corporate area of expertise is still limited, the need for a Web framework, the corresponding expansion of the following: (1) Extending Web Framework core components, as well as data validation components, increased exception handling components and logging utility class. (2) expansion of the tag library, including the drop-down data source label, tree control label, date and time format of the control tag, the page permissions tab and page elements, access control labels, navigation tabs on the location of the page, as well as abnormal display and labels.

382
Information Technology for Manufacturing Systems III Increase access to the framework of process management, graphics management, and unified security management, report management utility class. For example, the process management utility class used to implement the generated process instance, the process pass (including the normal transfer and jump transfer) process view, monitor the process flow and other functions, and provide page customization utility, according to the data set, the format parameters automatically generated JSP files.
Data sets defined components, the operating components of data sets loaded components, data sets. The data set defined components to define data query, stored procedure mapping, data queries, stored procedure defined to store the XML document property is set to include the code columns, column names, data types, extended attributes, the main foreign key, the update flag. Data set to load components will be stored in XML for dynamic loading, complete the two-dimensional table in the relational database and object-oriented systems object mapping process [8]. Operating components of the data set encapsulates the data access details on the background of the relational database application to access the system through a data set of operating components, both abstract data where the data source, and abstract database CRUD (Create, Replace, Update, Delete) logic., as is shown by equation6.
[ ] Application J2EE technology design and implementation of logistics management system using B / S multi-tier architecture, so that application data is limited in the corresponding layer, reducing the coupling between the layers of data, to improve the overall framework can maintain and scalability. Windows XP operating system using Visual VB.net to achieve the above rule set and computing algorithm. For randomly generated data sets, the relationship between the probabilities of 85%, we do the extended test, the number of objects in increments of 23, recorded by the sub-formal context. The paper proposes the design and implementation of the logistics management system based on J2EE technology, the results shown in Figure 2. Business infrastructure platform and customer management and business are more common infrastructure platform for application software development. Interaction between software and hardware, and management of operating system platform, database platform, J2EE infrastructure platform to solve the interaction between system software and operating system platforms and management issues, J2EE business infrastructure platform to solve a business description of the application software and operating system platforms, the interaction between the management of the database platform, J2EE infrastructure platform.
In this paper, on the basis of analysis of enterprise management information system "open, interconnected, integrated and practical needs, the logistics management system of the J2EE business infrastructure platform-based design and implement solutions. Described the key technologies of the system is involved in the J2EE technology web application framework, workflow platform, and rights management platform, report management platform, and introduced the system of functional modules and features.

Summary
The paper proposes the design and implementation of the logistics management system based on J2EE technology. Logistics Management System Design and Implementation of J2EE business infrastructure platform based on the hierarchical structure of the software platform, J2EE business infrastructure platform provided by the business component, software services, application and database platform, J2EE infrastructure platform isolation improve software reusability, can improve the efficiency of the development, system development and application of the key.


extfieldsofstudy:
Mathematics
Computer Science

s2fieldsofstudy:
Computer Science
Mathematics

text:
Distributed Alternating Direction Method of Multipliers

We consider a network of agents that are cooperatively solving a global unconstrained optimization problem, where the objective function is the sum of privately known local objective functions of the agents. Recent literature on distributed optimization methods for solving this problem focused on subgradient based methods, which typically converge at the rate O (1/√k), where k is the number of iterations. In this paper, k we introduce a new distributed optimization algorithm based on Alternating Direction Method of Multipliers (ADMM), which is a classical method for sequentially decomposing optimization problems with coupled constraints. We show that this algorithm converges at the rate O (1/k).

I. INTRODUCTION
Some of the problems in machine learning and statistical inference, LASSO (least-absolute shrinkage and selection operator) for instance, can be characterized by a network of agents, where each of the agents is associated with a local cost function and the system objective is to minimize the sum of all local costs. The local cost functions are often determined by a large private data set, which makes passing information regarding the local cost function very difficult. These problems motivated research interest in developing distributed method for solving optimization problems [4], [7], [12], [13], [15], [18], [19].
There are two general types of distributed algorithms. The first type is (sub)gradient based, where at each step a (sub)gradient related step is taken, followed by averaging with neighbors. The computation at each step can be very inexpensive and lead to distributed implementations [4], [9], [8], [11], [13], [14]. The best known rate of convergence for subgradient based distributed methods is O( 1 √ k ). The second type of distributed algorithm is for solving constrained problems and it relies on dual methods. In these methods, at each step for a fixed dual variable, the primal variables are solved to minimize some Lagrangian related function, then the dual variables are updated accordingly [3], [6], [7], [17]. This type of methods is preferred when each agent can solve the local optimization problem efficiently. One of the well known method of this kind is the Alternating Direction Method of Multipliers (ADMM), which decomposes the original problem into two sub-problems, sequentially solves them and updates the dual variables associated with a coupling constraint at each iteration. The best known rate of convergence for the classic ADMM algorithm is O( 1 k ).
This work was supported by National Science Foundation under Career grant DMI-0545910 and AFOSR MURI FA9550-09-1-0538.
† Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology The drawback of the standard ADMM method is that it partitions the problem into only two subproblems and thus cannot be implemented in a distributed way for a larger network. In recent works [5], [16] and [10], distributed ADMM algorithms tailored for specific machine learning problems and parameter estimation in wireless sensor networks have been proposed without convergence rate analysis. In this work, we propose a distributed ADMM algorithm for an unconstrained general optimization problem over an Nagent network. We first transform the problem into one with constraints and then distribute the problem to N agents. Each agent implements the algorithm using local cost functions and information obtained via communication with neighbors. We also establish that the proposed algorithm has O( 1 k ) rate of convergence.
In the distributed ADMM algorithm, the updates of the agents are done in a sequential order. 1 In this sense, our proposed method is closely related to incremental distributed algorithms studied in the literature [2], [15], where each agent takes turn to update the system wide decision variable and passes the updated variable to the network. The difference here is that each agent maintains and updates its local estimate. The analysis in this paper is related to [3] and [6]. In both of the works, convergence analysis are done to the standard ADMM algorithm. One of our contributions is to extend the analysis to the distributed ADMM algorithm with N agents.
The rest of the paper is organized as follows. Section II defines the problem formulation and equivalent transformation. In Section III, we review the standard ADMM algorithm and develop the distributed ADMM method. In Section IV, we present the convergence analysis of the distributed ADMM algorithm. Section V contains our concluding remarks.

Basic Notation and Notions:
A vector is viewed as a column vector, unless clearly stated otherwise. For a matrix A, we write A ij to denote the matrix entry in the i th row and j th column, and [A] i to denote the i th column of the matrix A, and [A] j to denote the j th row of the matrix A. For a vector x, x i denotes the i th component of the vector. We use x and A to denote the transpose of a vector x and a matrix A respectively. For a real-valued function f : X → R, where X is a subset of R n , the gradient vector of f at x in X are denoted by ∇f (x). We use standard Euclidean norm unless otherwise noted, i.e., for a vector x in R n , ||x|| = n i=1 x 2 i 1 2 .

II. FORMULATION
We consider a network, represented by an undirected connected simple graph with N nodes and M edges, G = {V, E}, where the set V denotes the set of nodes and the set E denotes the set of undirected edges. The nodes can be considered as agents in many applications, we will use the two terms interchangeably. We assume that nodes are ordered from 1 to N and use e ij to denote the edge between nodes i and j with i < j.
Each node is associated with a cost function f i : R → R, which is not necessarily differentiable. The nodes in the network are collectively solving the following unconstrained optimization problem We assume that each f i is locally known by agent i only. 2 We next consider a reformulation of problem (1) which will be used in the development of our distributed algorithm. In particular, we will introduce a separate decision variable x i for each of the nodes and impose the constraint x i = x j for all pairs (i, j) with e ij in set E, which guarantees that the node decision variables are equal, i.e., x i =x for all nodes i for somex. We write the transformed problem compactly by introducing the edge-node incidence matrix, which represents the network topology. The edge-node incidence matrix of network G, denoted by A, has dimension M × N . Each row of matrix A corresponds to an edge in the graph and each column represent an agent. The row corresponding to the edge e ij , which we denote by [A] eij , has 1 in the i th column, −1 in the j th column and 0 in the other columns, i.e., 3 For instance, the edge-node incidence matrix for the network in Figure 1 is given by The analysis in this paper can be extended to the case when the f i are multi-dimensional functions. To highlight the main ideas, we restrict attention to the case where the f i are one-dimensional here. 3 We adopt the convention that the smaller column has entry 1 and the larger one has −1. The analysis holds for other consistent way of writing the edge-node incidence matrix, for example, with −1 at i th column and 1 at j th column. With the edge-node incidence matrix, we can now rewrite problem (1) as The constraint Ax = 0 is a compact way of writing x i = x j for nodes i and j which are connected by an edge. For the rest of the paper, we will focus on solving problem (2). We denote the optimal value of problem (2) by F * . For notational convenience, we define the function F : We denote by L : R N × R M → R the Lagrangian function given by where λ in R M is the Lagrange multiplier vector associated with the constraint Ax = 0. We impose the following standard assumptions on the optimization problem.
Assumption 1: (Convexity) Each of the cost function f i : R → R is closed, proper and strictly convex.
for all x in R N and λ in R M . Assumption 1 implies that F (x) [cf. Eq. (3)] and therefore L(x, λ * ) is strictly convex in x. This assumption will be used in our convergence analysis. Assumption 2 implies that problem (2) has an optimal solution, which we denote by x * .
III. ALGORITHM In this section, we develop our distributed optimization algorithm, which is a primal dual algorithm motivated by the alternating direction method of multipliers (ADMM) (see [3] for a recent survey on ADMM). The standard ADMM algorithm involves decomposing the decision vector into subvectors, updating each subvector sequentially (using the most recent value for the rest of the subvectors) by minimizing an augmented Lagrangian function, and finally updating the Lagrange multiplier corresponding to the constraint that couples the subvectors using a dual subgradient method. The ADMM algorithm has typically been used for solving problems in which the decision variable is decomposed into two subvectors, which are coupled with a linear constraint. Hence, it can be viewed as solving a 2-agent special case of problem (2). Here we extend the formulation to N subvectors (each corresponding to an agent) and develop an ADMM that can be implemented in a distributed manner over the connected network in which the agents are situated. We first present the standard ADMM formulation and algorithm and then present our distributed ADMM algorithm.

A. Preliminaries: Standard ADMM Algorithm
The standard ADMM algorithm solves the following prob- We consider the augmented Lagrangian function given by where µ is the Lagrange multiplier corresponding to the constraint F y + Dz = c and ρ is a positive scalar. The ADMM algorithm updates the primal variables y and z and the Lagrange multiplier µ as follows: Starting from some initial vector (y 0 , x 0 , µ 0 ) 5 , at iteration k ≥ 0, the variables are updated as Note that stepsize used in updating the Lagrange multiplier vector is the same as the augmented Lagrangian function parameter ρ.
The ADMM algorithm has an equivalent representation, which we will use to develop our distributed ADMM algorithm. The equivalent representation is based on the following transformation. The last two terms in the augmented Lagrangian function [cf. Eq. (7)] satisfy µ (F y + Dz − c) + 4 This subsection follows closely the development in [3] 5 We use superscripts to denote the iteration number where we used the identity 2a b + ||b|| 2 = ||a + b|| 2 − ||a|| 2 replacing a = µ and b = F y+Dz−c. Therefore, by ignoring terms which are independent of the minimization variables, updates (8) and (9) can be expressed as We will now use updates (11), (12) and (10) to develop the distributed ADMM algorithm.

B. Distributed ADMM Algorithm
In the distributed ADMM algorithm, we associate a dual variable λ ij with the constraint x i = x j on edge e ij , and denote by λ the vector of dual variables, i.e., [λ ij ] ij,eij ∈E . Each agent i keeps a local decision estimate x i in R and a vector of dual variables λ ki with k < i. We say agent i owns the dual variable λ ki for k < i and agent i updates the dual variable.
To facilitate the development of our algorithm, we introduce the following notation. We partition the neighbors of a node i into two sets, which we call predecessors and successors of node i, denoted by P (i) and S(i). The set of the predecessors of i consists of neighbors whose index is smaller than i, i.e., P (i) = {j | e ji ∈ E, j < i}, and successors of i are the neighbors with index larger than i, i.e., S(i) = {j | e ij ∈ E, i < j}. Since the graph G is a simple graph, i.e., no edge of the type e ii , the set P (i)∪S(i) includes all neighbors of node i.
Following the development of ADMM described in the previous section, we use an augmented Lagrangian approach to solve problem (2) and use scalar β > 0 as the penalty parameter. We note that each row of the constraint Ax = 0 corresponds to x i −x j = 0 for some i < j with e ij in the set E and the distributed ADMM algorithm for solving problem (2) is given as follows: A Initialization: choose some arbitrary x 0 i in R for i = 1, . . . , N , which are not necessarily all equal. B For k ≥ 0, a Each agent i updates its estimate x k i in a sequential order with Fig. 2. Sample algorithm evolution.
b Each agent updates λ ji that he owns, for all j in P (i), Remarks: We assume that the nodes are ordered. In the above algorithm, at each iteration, the agents update in a sequential way, i.e., at iteration k agent i updates before agent j if i < j. In [20] we relax this assumption and the node update is determined randomly in a distributed manner.
We assume that as soon as the variables x k i and λ k ji are available to agent i, all of its neighbors can also access the data by local information exchange. The above algorithm is well defined, since the step B.a and B.b are implemented in a sequential way, the value of x k+1 j for j in P (i) and x k j for j in S(i) are available for agent i during its turn to update. The algorithm can be implemented in a distributed way, since the only communication (of scalar information x k j and λ k ji ) is with immediate neighbors at each step. This method is related to incremental methods, where each of the agents take turn to update the system wide decision variable and passes the updated variable to the network. The major difference here is that each agent has a local copy of the decision variable, which is not publicly accessible by all the other agents.
For illustration purposes, in Figure 2, we show a snapshot of the distributed ADMM algorithm applied to the network in Figure 1. In the figure, nodes 1 and 2 have completed the (k + 1) th updates, and node 3 (highlighted in yellow) is the next one to update. The predecessor of node 3, i.e.,

IV. CONVERGENCE ANALYSIS
In this section, we present our analysis of the convergence properties of the distributed ADMM algorithm presented in the last section and show that it has a O( 1 k ) rate of convergence, where we count the updates (13) and (14) for all i as one iteration. The analysis here is inspired by the work in [6] and [3], both of which analyzed the standard ADMM algorithm applicable to the special case of a 2node network. We will first introduce some notation for representational convenience, and derive three lemmas, all of which will then be used to establish the convergence properties of the algorithm.
We denote by B, a matrix B in R M × R N given by B = min{0, A}, where the maximization is taken element-wise. For example, the B matrix for the network given in Figure  1 has the following form, From the definition of matrix B, it follows that each row of matrix B corresponds to one edge (i, j) with i < j and consists of exactly one entry of −1 at position j. We denote by [B] eij the row of B corresponding to the edge e ij . Our analysis of the convergence relies on a key relation derived from the optimality of x k i at each iteration. This is established in the following lemma.
Lemma 4.1: Let {x k , λ k } be the iterates generated by our distributed ADMM algorithm for problem (2), with vector and vector λ k = [λ k ij ] ij,eij ∈E . Then the following relation holds for all k, for any x in R N , where matrix A is the edge-node incidence matrix of the network and matrix B = min{0, A}. Proof: We denote by g i : R → R the function and from update (13), we have x k+1 i is the optimizer of g k i +f i . The optimality implies there exists some subgradient The above two relations yield We then substitute ∇g k i using the definition of function g [cf. Eq. (16)] into the above relation and obtain, (14), By using the definition of the matrix A, we can rewrite the preceding inequality as We then sum the above relation over i = 1, . . . , N , and obtain By using the definition of matrices A and B, we can rewrite the terms compactly in matrix representation as − The preceding three relations can be combined to establish the desired relation.
We next relate the terms on the left hand side of relation (15) to a combination of vector norms. This is important since we can bound each of the norm term as nonnegative, which will then be used to establish convergence properties by forming a telescoping series.
Lemma 4.2: Let {x k , λ k } be the iterates generated by our distributed ADMM algorithm for problem (2), with vector and vector λ k = [λ k ij ] ij,eij ∈E . Let matrix A be the edge-node incidence matrix of the network and matrix B satisfy B = min{0, A}. Then the following relation holds for all k, (17) Proof: The proof relies on rewriting the terms on the left hand side of (17), using algebraic manipulation and techniques similar to the appendix of [3]. Most of the manipulation are based on two observations: λ k+1 = λ k −βAx k+1 and ||a + b|| 2 = ||a|| 2 + ||b|| 2 + 2a b for arbitrary vectors a and b. Due to space constraints, we omit the proof here, interested readers can find the full proof in [20]. We now present a simple lemma based on saddle point properties of the Lagrangian function.  , λ), where x is in R N and λ is in R M , the following relation holds The above relation holds for all λ and thus Ax * = 0.
With the three preceding lemmas, we can now establish the main result of the paper, i.e., the O( 1 k ) rate of convergence of the distributed ADMM algorithm. Theorem 4.4: Let {x k , λ k } be the iterates generated by our distributed ADMM algorithm for problem (2), with vector x k = [x k 1 , x k 2 , . . . , x k N ] and vector λ k = [λ k ij ] ij,eij ∈E . Let matrix A be the edge-node incidence matrix of the network and matrix B satisfy B = min{0, A}. Let y k = 1 k k−1 s=0 x s be the ergodic average of x k up to time t, then the following relation holds for all t, Proof: The first inequality follows immediately from definition of the saddle point of the Lagrangian function [cf. relation (5)].
We now prove the second inequality in Eq. (19). By setting x = x * in relation (15) from Lemma 4.1, we obtain for all iteration s, Due to feasibility of the optimal solution x * , we have Ax * = 0, and the above relation is equivalent to By adding and subtracting the term (λ * ) Ax s+1 from the right hand side of the preceding relation, we have where we used the identity a = a for a scalar a. We now use Lemma 4.2 to equivalently express the preceding inequality as, which holds true for all s. We sum the preceding inequality over s = 0, 1, . . . , k − 1 and after telescoping cancelation, we obtain Due to the convexity of function F , we have k−1 s=0 F (x s ) ≥ kF (y k ), and thus using the definition for y k , we have kF (x * ) − kF (y k ) + (λ * ) Ay k By multiplying both sides by −k, we have established the desired relation.
The above relation combined with the definition of the Lagrangian function [cf. Eq. (4)] and Eq. (18) yield the desired relation. Due to strict convexity of the function F [cf. Assumption 1] and linearity of the term λ * Ax, we have the function L(x, λ * ) is strictly convex in x. Therefore we conclude that the function L(x, λ * ) has a unique minimizer, i.e., x * in Assumption 2. Hence Theorem 4.4 guarantees that the value of the Lagrangian function obtained by the ergodic average sequence y k , i.e., L(y k , λ * ), converges to L(x * , λ * ) = F * at the rate of O( 1 k ). In practice, one might implement the algorithm with one additional variable y k i to keep the ergodic average of x k i to achieve the O( 1 k ) rate of convergence. 6 V. CONCLUSIONS In this paper, we develop a distributed ADMM algorithm for an N -agent network, where each agent takes turn to update its local variable. We show that the proposed algorithm achieves a rate of O( 1 k ) rate of convergence, which is the best known rate for dual methods based distributed algorithms. In ongoing work, we are extending this analysis to the algorithm when agents update asynchronously (in some randomized order) and for constrained optimization problems [20].