File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: An efficient algorithm for optimizing whole genome alignment with noise

TitleAn efficient algorithm for optimizing whole genome alignment with noise
Authors
Issue Date2004
PublisherOxford University Press. The Journal's web site is located at http://bioinformatics.oxfordjournals.org/
Citation
Bioinformatics, 2004, v. 20 n. 16, p. 2676-2684 How to Cite?
AbstractMotivation: 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). © Oxford University Press 2004; all rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/43629
ISSN
2015 Impact Factor: 5.766
2015 SCImago Journal Rankings: 4.643
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorWong, PWHen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLu, Nen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorYiu, SMen_HK
dc.date.accessioned2007-03-23T04:50:49Z-
dc.date.available2007-03-23T04:50:49Z-
dc.date.issued2004en_HK
dc.identifier.citationBioinformatics, 2004, v. 20 n. 16, p. 2676-2684en_HK
dc.identifier.issn1367-4803en_HK
dc.identifier.urihttp://hdl.handle.net/10722/43629-
dc.description.abstractMotivation: 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). © Oxford University Press 2004; all rights reserved.en_HK
dc.format.extent275454 bytes-
dc.format.extent25600 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/msword-
dc.languageengen_HK
dc.publisherOxford University Press. The Journal's web site is located at http://bioinformatics.oxfordjournals.org/en_HK
dc.relation.ispartofBioinformaticsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subject.meshAlgorithmsen_HK
dc.subject.meshChromosome mapping - methodsen_HK
dc.subject.meshSequence alignment - methodsen_HK
dc.subject.meshSequence analysis, dna - methodsen_HK
dc.subject.meshSequence analysis, protein - methodsen_HK
dc.titleAn efficient algorithm for optimizing whole genome alignment with noiseen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1471-2105&volume=20&issue=16&spage=2676&epage=2684&date=2004&atitle=An+efficient+algorithm+for+optimizing+whole+genome+alignment+with+noiseen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.emailYiu, SM:smyiu@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.identifier.authorityYiu, SM=rp00207en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1093/bioinformatics/bth308en_HK
dc.identifier.pmid15145812-
dc.identifier.scopuseid_2-s2.0-8844240664en_HK
dc.identifier.hkuros107321-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-8844240664&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume20en_HK
dc.identifier.issue16en_HK
dc.identifier.spage2676en_HK
dc.identifier.epage2684en_HK
dc.identifier.isiWOS:000225250100022-
dc.publisher.placeUnited Kingdomen_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLu, N=7101614722en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridYiu, SM=7003282240en_HK
dc.identifier.citeulike11616798-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats