Efficient discovery of conserved patterns using a pattern graph
Inge Jonassen · Computer applications in the biosciences · 1997
Motivation: We have previously reported an algorithm for discovering patterns conserved in sets of related unaligned protein sequences. The algorithm was implemented in a program called Pratt. Pratt allows the user to define a class of patterns (e.g. the degree of ambiguity allowed and the length and number of gaps), and is then guaranteed to find the conserved patterns in this class scoring highest according to a defined fitness measure. In many cases, this version of Pratt was very efficient, but in other cases it was too time consuming to be applied. Hence, a more efficient algorithm was needed. Results:In this paper, we describe a new and improved searching strategy that has two main advantages over the old strategy. First, it allows for easier integration with programs for multiple sequence alignment and data base search. Secondly, it makes it possible to use branch-and-bound search, and heuristics, to speed up the search. The new search strategy has been implemented in a new version of the Pratt program. Availability: The source code for the Pratt programs can be obtained via the World Wide Web: http:llwwMi.ii.uib.nol ingelPratt.html or usinganonymousftp from ftp://ftp.ii.uib.no/ pub/bio/Pratt. Contact:E-mail: inge@ii.uib.no
Cited by 151 works. doi:10.1093/bioinformatics/13.5.509 Open-access PDF
Authors
References
- CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice
- The PROSITE database, its status in 1995
- Automatic generation of primary sequence patterns from sets of related protein sequences.
- SRS—an indexing and retrieval tool for flat file data libraries
- The ENZYME data bank.
- Detection of conserved segments in proteins: iterative scanning of sequence databases with alignment blocks.
- Finding patterns common to a set of strings
- Finding sequence motifs in groups of functionally related proteins.
- A search for common patterns in many sequences
- Finding flexible patterns in unaligned protein sequences