File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Efficient algorithms for optimizing whole genome alignment with noise

TitleEfficient algorithms for optimizing whole genome alignment with noise
Authors
Issue Date2003
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2003, v. 2906, p. 364-374 How to Cite?
AbstractGiven the genomes (DNA) of two related species, the whole genome alignment problem is to locate regions on the genomes that possibly contain genes conserved over the two species. Motivated by existing heuristic-based software tools, we initiate the study of optimization problems that attempt to uncover conserved genes with a global concern. Another interesting feature in our formulation is the tolerance of noise. Yet this makes the optimization problems more complicated; a brute-force approach takes time exponential in the noise level. In this paper we show how an insight into the problem 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 algorithms on a PC. It is exciting to see that when compared with the most popular whole genome alignment software (MUMMER) on real data sets, the new algorithms consistently uncover more conserved genes (that have been published by GenBank), while preserving the preciseness of the output. © Springer-Verlag Berlin Heidelberg 2003.
Persistent Identifierhttp://hdl.handle.net/10722/93167
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLu, Nen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorWong, PWHen_HK
dc.contributor.authorYiu, SMen_HK
dc.date.accessioned2010-09-25T14:52:55Z-
dc.date.available2010-09-25T14:52:55Z-
dc.date.issued2003en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2003, v. 2906, p. 364-374en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93167-
dc.description.abstractGiven the genomes (DNA) of two related species, the whole genome alignment problem is to locate regions on the genomes that possibly contain genes conserved over the two species. Motivated by existing heuristic-based software tools, we initiate the study of optimization problems that attempt to uncover conserved genes with a global concern. Another interesting feature in our formulation is the tolerance of noise. Yet this makes the optimization problems more complicated; a brute-force approach takes time exponential in the noise level. In this paper we show how an insight into the problem 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 algorithms on a PC. It is exciting to see that when compared with the most popular whole genome alignment software (MUMMER) on real data sets, the new algorithms consistently uncover more conserved genes (that have been published by GenBank), while preserving the preciseness of the output. © Springer-Verlag Berlin Heidelberg 2003.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.titleEfficient algorithms for optimizing whole genome alignment with noiseen_HK
dc.typeArticleen_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.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-35248890424en_HK
dc.identifier.hkuros91586en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-35248890424&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume2906en_HK
dc.identifier.spage364en_HK
dc.identifier.epage374en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLu, N=7101614722en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK
dc.identifier.scopusauthoridYiu, SM=7003282240en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats