Cargando…
Simultaneous identification of long similar substrings in large sets of sequences
BACKGROUND: Sequence comparison faces new challenges today, with many complete genomes and large libraries of transcripts known. Gene annotation pipelines match these sequences in order to identify genes and their alternative splice forms. However, the software currently available cannot simultaneou...
Autores principales: | , , |
---|---|
Formato: | Texto |
Lenguaje: | English |
Publicado: |
BioMed Central
2007
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1892095/ https://www.ncbi.nlm.nih.gov/pubmed/17570866 http://dx.doi.org/10.1186/1471-2105-8-S5-S7 |
_version_ | 1782133826010480640 |
---|---|
author | Kleffe, Jürgen Möller, Friedrich Wittig, Burghardt |
author_facet | Kleffe, Jürgen Möller, Friedrich Wittig, Burghardt |
author_sort | Kleffe, Jürgen |
collection | PubMed |
description | BACKGROUND: Sequence comparison faces new challenges today, with many complete genomes and large libraries of transcripts known. Gene annotation pipelines match these sequences in order to identify genes and their alternative splice forms. However, the software currently available cannot simultaneously compare sets of sequences as large as necessary especially if errors must be considered. RESULTS: We therefore present a new algorithm for the identification of almost perfectly matching substrings in very large sets of sequences. Its implementation, called ClustDB, is considerably faster and can handle 16 times more data than VMATCH, the most memory efficient exact program known today. ClustDB simultaneously generates large sets of exactly matching substrings of a given minimum length as seeds for a novel method of match extension with errors. It generates alignments of maximum length with a considered maximum number of errors within each overlapping window of a given size. Such alignments are not optimal in the usual sense but faster to calculate and often more appropriate than traditional alignments for genomic sequence comparisons, EST and full-length cDNA matching, and genomic sequence assembly. The method is used to check the overlaps and to reveal possible assembly errors for 1377 Medicago truncatula BAC-size sequences published at . CONCLUSION: The program ClustDB proves that window alignment is an efficient way to find long sequence sections of homogenous alignment quality, as expected in case of random errors, and to detect systematic errors resulting from sequence contaminations. Such inserts are systematically overlooked in long alignments controlled by only tuning penalties for mismatches and gaps. ClustDB is freely available for academic use. |
format | Text |
id | pubmed-1892095 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2007 |
publisher | BioMed Central |
record_format | MEDLINE/PubMed |
spelling | pubmed-18920952007-06-15 Simultaneous identification of long similar substrings in large sets of sequences Kleffe, Jürgen Möller, Friedrich Wittig, Burghardt BMC Bioinformatics Research BACKGROUND: Sequence comparison faces new challenges today, with many complete genomes and large libraries of transcripts known. Gene annotation pipelines match these sequences in order to identify genes and their alternative splice forms. However, the software currently available cannot simultaneously compare sets of sequences as large as necessary especially if errors must be considered. RESULTS: We therefore present a new algorithm for the identification of almost perfectly matching substrings in very large sets of sequences. Its implementation, called ClustDB, is considerably faster and can handle 16 times more data than VMATCH, the most memory efficient exact program known today. ClustDB simultaneously generates large sets of exactly matching substrings of a given minimum length as seeds for a novel method of match extension with errors. It generates alignments of maximum length with a considered maximum number of errors within each overlapping window of a given size. Such alignments are not optimal in the usual sense but faster to calculate and often more appropriate than traditional alignments for genomic sequence comparisons, EST and full-length cDNA matching, and genomic sequence assembly. The method is used to check the overlaps and to reveal possible assembly errors for 1377 Medicago truncatula BAC-size sequences published at . CONCLUSION: The program ClustDB proves that window alignment is an efficient way to find long sequence sections of homogenous alignment quality, as expected in case of random errors, and to detect systematic errors resulting from sequence contaminations. Such inserts are systematically overlooked in long alignments controlled by only tuning penalties for mismatches and gaps. ClustDB is freely available for academic use. BioMed Central 2007-05-24 /pmc/articles/PMC1892095/ /pubmed/17570866 http://dx.doi.org/10.1186/1471-2105-8-S5-S7 Text en Copyright © 2007 Kleffe et al; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an open access article distributed under the terms of the Creative Commons Attribution License ( (http://creativecommons.org/licenses/by/2.0) ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
spellingShingle | Research Kleffe, Jürgen Möller, Friedrich Wittig, Burghardt Simultaneous identification of long similar substrings in large sets of sequences |
title | Simultaneous identification of long similar substrings in large sets of sequences |
title_full | Simultaneous identification of long similar substrings in large sets of sequences |
title_fullStr | Simultaneous identification of long similar substrings in large sets of sequences |
title_full_unstemmed | Simultaneous identification of long similar substrings in large sets of sequences |
title_short | Simultaneous identification of long similar substrings in large sets of sequences |
title_sort | simultaneous identification of long similar substrings in large sets of sequences |
topic | Research |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1892095/ https://www.ncbi.nlm.nih.gov/pubmed/17570866 http://dx.doi.org/10.1186/1471-2105-8-S5-S7 |
work_keys_str_mv | AT kleffejurgen simultaneousidentificationoflongsimilarsubstringsinlargesetsofsequences AT mollerfriedrich simultaneousidentificationoflongsimilarsubstringsinlargesetsofsequences AT wittigburghardt simultaneousidentificationoflongsimilarsubstringsinlargesetsofsequences |