title: LocalAli: an evolutionary-based local alignment approach to identify functionally conserved modules in multiple networks.
abstract: BACKGROUND
  Sequences and protein interaction data are of significance to understand the underlying molecular mechanism of organisms. Local network alignment is one of key systematic ways for predicting protein functions, identifying functional modules and understanding the phylogeny from these data. Most of currently existing tools, however, encounter their limitations, which are mainly concerned with scoring scheme, speed and scalability. Therefore, there are growing demands for sophisticated network evolution models and efficient local alignment algorithms.
  
  
  RESULTS
  We developed a fast and scalable local network alignment tool called LocalAli for the identification of functionally conserved modules in multiple networks. In this algorithm, we firstly proposed a new framework to reconstruct the evolution history of conserved modules based on a maximum-parsimony evolutionary model. By relying on this model, LocalAli facilitates interpretation of resulting local alignments in terms of conserved modules, which have been evolved from a common ancestral module through a series of evolutionary events. A meta-heuristic method simulated annealing was used to search for the optimal or near-optimal inner nodes (i.e. ancestral modules) of the evolutionary tree. To evaluate the performance and the statistical significance, LocalAli were tested on 26 real datasets and 1040 randomly generated datasets. The results suggest that LocalAli outperforms all existing algorithms in terms of coverage, consistency and scalability, meanwhile retains a high precision in the identification of functionally coherent subnetworks.
  
  
  BACKGROUND
  The source code and test datasets are freely available for download under the GNU GPL v3 license at https://code.google.com/p/localali/.
  
  
  BACKGROUND
  jialu.hu@fu-berlin.de or knut.reinert@fu-berlin.de.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Mathematics and Computer Science, Freie Universität Berlin, Takustrasse 9, 14195 Berlin, Germany.
authors.forename: Jialu
authors.initials: J
authors.lastname: Hu
authors.affiliation: Department of Mathematics and Computer Science, Freie Universität Berlin, Takustrasse 9, 14195 Berlin, Germany.
authors.forename: Knut
authors.initials: K
authors.lastname: Reinert
mesh_terms: D000465:Algorithms; D005075:Biological Evolution; D019295:Computational Biology; D030562:Databases, Protein; D053263:Gene Regulatory Networks; D006801:Humans; D010802:Phylogeny; D025941:Protein Interaction Mapping / Q000379:methods*; D011506:Proteins; D016415:Sequence Alignment / Q000379:methods*; D012984:Software
chemical_list: D011506:Proteins