Skip Navigation


MBE Advance Access originally published online on May 30, 2003
This Article
Right arrow Full Text Freely available
Right arrow FREE Full Text (PDF) Freely available
Right arrow Supplementary Material
Right arrow All Versions of this Article:
20/8/1299    most recent
msg139v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (3)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Shih, A. C.-C.
Right arrow Articles by Li, W.-H.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Shih, A. C.-C.
Right arrow Articles by Li, W.-H.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Mol. Biol. Evol. 20(8):1299-1309. 2003
DOI: 10.1093/molbev/msg139
© 2003 by the Society for Molecular Biology and Evolution. ISSN: 0737-4038

GS-Aligner: A Novel Tool for Aligning Genomic Sequences Using Bit-Level Operations

Arthur Chun-Chieh Shih*,{dagger} and Wen-Hsiung Li{dagger},{ddagger},

* Institute of Information Science, Academia Sinica, Taipei, Taiwan
{dagger} Department of Ecology and Evolution, University of Chicago
{ddagger} Genomics Research Center, Academia Sinica, Taipei, Taiwan

E-mail: whli{at}uchicago.edu.

A novel algorithm, GS-Aligner, that uses bit-level operations was developed for aligning genomic sequences. GS-Aligner is efficient in terms of both time and space for aligning two very long genomic sequences and for identifying genomic rearrangements such as translocations and inversions. It is suitable for aligning fairly divergent sequences such as human and mouse genomic sequences. It consists of several efficient components: bit-level coding, search for matching segments between the two sequences as alignment anchors, longest increasing subsequence (LIS), and optimal local alignment. Efforts have been made to reduce the execution time of the program to make it truly practical for aligning very long sequences. Empirical tests suggest that for relatively divergent sequences such as sequences from different mammalian orders or from a mammal and a nonmammalian vertebrate GS-Aligner performs better than existing methods. The program and data can be downloaded from http://pondside.uchicago.edu/~lilab/ and http://webcollab.iis.sinica.edu.tw/~biocom.

Key Words: genomic sequences • sequence alignment • conserved regions • translocations • inversions


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Mol Biol EvolHome page
L. Zhang, H. H. S. Lu, W.-y. Chung, J. Yang, and W.-H. Li
Patterns of Segmental Duplication in the Human Genome
Mol. Biol. Evol., January 1, 2005; 22(1): 135 - 141.
[Abstract] [Full Text] [PDF]


Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.