File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Article: Efficient algorithms for optimizing whole genome alignment with noise
Title | Efficient algorithms for optimizing whole genome alignment with noise |
---|---|
Authors | |
Issue Date | 2003 |
Publisher | Springer 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? |
Abstract | Given 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 Identifier | http://hdl.handle.net/10722/93167 |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | Lu, N | en_HK |
dc.contributor.author | Ting, HF | en_HK |
dc.contributor.author | Wong, PWH | en_HK |
dc.contributor.author | Yiu, SM | en_HK |
dc.date.accessioned | 2010-09-25T14:52:55Z | - |
dc.date.available | 2010-09-25T14:52:55Z | - |
dc.date.issued | 2003 | en_HK |
dc.identifier.citation | Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2003, v. 2906, p. 364-374 | en_HK |
dc.identifier.issn | 0302-9743 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/93167 | - |
dc.description.abstract | Given 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.language | eng | en_HK |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | en_HK |
dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | en_HK |
dc.title | Efficient algorithms for optimizing whole genome alignment with noise | en_HK |
dc.type | Article | en_HK |
dc.identifier.email | Lam, TW:twlam@cs.hku.hk | en_HK |
dc.identifier.email | Ting, HF:hfting@cs.hku.hk | en_HK |
dc.identifier.email | Yiu, SM:smyiu@cs.hku.hk | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.identifier.authority | Ting, HF=rp00177 | en_HK |
dc.identifier.authority | Yiu, SM=rp00207 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.scopus | eid_2-s2.0-35248890424 | en_HK |
dc.identifier.hkuros | 91586 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-35248890424&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 2906 | en_HK |
dc.identifier.spage | 364 | en_HK |
dc.identifier.epage | 374 | en_HK |
dc.publisher.place | Germany | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | Lu, N=7101614722 | en_HK |
dc.identifier.scopusauthorid | Ting, HF=7005654198 | en_HK |
dc.identifier.scopusauthorid | Wong, PWH=9734871500 | en_HK |
dc.identifier.scopusauthorid | Yiu, SM=7003282240 | en_HK |
dc.identifier.issnl | 0302-9743 | - |