Tree pattern matching in phylogenetic trees: automatic search for orthologs or paralogs in homologous gene sequence databases.
BACKGROUND
Comparative sequence analysis is widely used to study genome function and evolution. This approach first requires the identification of homologous genes and then the interpretation of their homology relationships (orthology or paralogy). To provide help in this complex task, we developed three databases of homologous genes containing sequences, multiple alignments and phylogenetic trees: HOBACGEN, HOVERGEN and HOGENOM. In this paper, we present two new tools for automating the search for orthologs or paralogs in these databases.


RESULTS
First, we have developed and implemented an algorithm to infer speciation and duplication events by comparison of gene and species trees (tree reconciliation). Second, we have developed a general method to search in our databases the gene families for which the tree topology matches a peculiar tree pattern. This algorithm of unordered tree pattern matching has been implemented in the FamFetch graphical interface. With the help of a graphical editor, the user can specify the topology of the tree pattern, and set constraints on its nodes and leaves. Then, this pattern is compared with all the phylogenetic trees of the database, to retrieve the families in which one or several occurrences of this pattern are found. By specifying ad hoc patterns, it is therefore possible to identify orthologs in our databases.
Dufayard
Jean-François
JF
INRIA Rhône-Alpes 38334 Montbonnot, Saint Ismier Cedex, France.
Duret
Laurent
L
Penel
Simon
S
Gouy
Manolo
M
Rechenmann
François
F
Perrière
Guy
G
D000465:Algorithms; D001185:Artificial Intelligence; D005075:Biological Evolution; D003628:Database Management Systems; D019143:Evolution, Molecular; D010363:Pattern Recognition, Automated / Q000379:methods*; D010802:Phylogeny; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid; D014584:User-Computer Interface