In:
Bioinformatics, Oxford University Press (OUP), Vol. 18, No. 12 ( 2002-12-01), p. 1673-1680
Abstract:
Motivation: As a first approximation, similarity between two long orthologous regions of genomes can be represented by a chain of local similarities. Within such a chain, pairs of successive similarities are collinear (non-conflicting), i.e. segments involved in the nth similarity precede in both sequences segments involved in the (n+1)th similarity. However, when all similarities between two long sequences are considered, usually there are many conflicts between them. Although some conflicts can be avoided by masking transposons or low-complexity sequences, selecting only those similarities that reflect orthology and, thus, belong to the evolutionarily true chain is not trivial. Results: We propose a simple, hierarchical algorithm of finding the true chain of local similarities. Starting from similarities with low P-values, we resolve each pairwise conflict by deleting a similarity with a higher P-value. This greedy approach constructs a chain of similarities faster than when a chain optimal with respect to some global criterion is sought, and makes more sense biologically. Availability: A software tool OWEN based on the proposed approach is described in the accompanying note and is freely available at ftp://ftp.ncbi.nih.gov/pub/kondrashov/owen Contact: kondrashov@ncbi.nlm.nih.gov Supplementary information: Algorithm Chain and examples of chains of local similarities are available at ftp://ftp.ncbi.nih.gov/pub/kondrashov/owen/extra * To whom correspondence should be addressed.
Type of Medium:
Online Resource
ISSN:
1367-4811
,
1367-4803
DOI:
10.1093/bioinformatics/18.12.1673
Language:
English
Publisher:
Oxford University Press (OUP)
Publication Date:
2002
detail.hit.zdb_id:
1468345-3
SSG:
12
