title: An efficient algorithm for optimizing whole genome alignment with noise.
abstract: BACKGROUND
  This paper is concerned with algorithms for aligning two whole genomes so as to identify regions that possibly contain conserved genes. Motivated by existing heuristic-based software tools, we initiate the study of an optimization problem that attempts to uncover conserved genes with a global concern. Another interesting feature in our formulation is the tolerance of noise, which also complicates the optimization problem. A brute-force approach takes time exponential in the noise level.
  
  
  RESULTS
  We show how an insight into the optimization structure can lead to a drastic improvement in the time and space requirement [precisely, to O(k2n2) and O(k2n), respectively, where n is the size of the input and k is the noise level]. The reduced space requirement allows us to implement the new algorithm, called MaxMinCluster, on a PC. It is exciting to see that when tested with different real data sets, MaxMinCluster consistently uncovers a high percentage of conserved genes that have been published by GenBank. Its performance is indeed favorably compared to MUMmer (perhaps the most popular software tool for uncovering conserved genes in a whole-genome scale).
  
  
  BACKGROUND
  The source code is available from the website http://www.csis.hku.hk/~colly/maxmincluster/ detailed proof of the propositions can also be found there.
authors.affiliation: Department of Computer Science, University of Hong Kong, Hong Kong. whwong@cs.hku.hk
authors.forename: Prudence W H
authors.initials: PW
authors.lastname: Wong
authors.forename: T W
authors.initials: TW
authors.lastname: Lam
authors.forename: N
authors.initials: N
authors.lastname: Lu
authors.forename: H F
authors.initials: HF
authors.lastname: Ting
authors.forename: S M
authors.initials: SM
authors.lastname: Yiu
mesh_terms: D000465:Algorithms; D002874:Chromosome Mapping / Q000379:methods*; D016000:Cluster Analysis; D017124:Conserved Sequence / Q000235:genetics; D010363:Pattern Recognition, Automated / Q000379:methods; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D017386:Sequence Homology, Amino Acid; D012689:Sequence Homology, Nucleic Acid; D013269:Stochastic Processes