Skip Navigation



MBE Advance Access published online on May 30, 2003
Molecular Biology and Evolution, doi:10.1093/molbev/msg139
Molecular Biology and Evolution © Society for Molecular Biology and Evolution 2003; all rights reserved
This Article
Right arrow Advance Access manuscript (PDF) Freely available
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 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 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?

Accepted April 1, 2003
© 2003 Society for Molecular Biology and Evolution

Original Articles

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

Arthur Chun-Chieh Shih 1 Wen-Hsiung Li 2*

1 Institute of Information Science, Academia Sinica, Taipei, Taiwan; Department of Ecology and Evolution, University of Chicago, Chicago, IL, USA
2 Department of Ecology and Evolution, University of Chicago, Chicago, IL, USA; Genomics Research Center, Academia Sinica, Taiwan

* To whom correspondence should be addressed. E-mail: whli{at}uchicago.edu.


  Abstract

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 non-mammalian 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
 BioinformaticsHome page
T.-C. Chu, T. Liu, D. T. Lee, G. C. Lee, and A. C.-C. Shih
GR-Aligner: an algorithm for aligning pairwise genomic sequences containing rearrangement events
Bioinformatics, September 1, 2009; 25(17): 2188 - 2193.
[Abstract] [Full Text] [PDF]

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.