Correspondence between unlabeled/different tips of different phylogenetic trees

Question

[rfm]

Greetings!

I've been thinking about and searching for strategies to combine information of phylogenetic trees. My problem is a little different than what is usually done. Suppose I have 2 phylogenetic trees, constructed from sequences of 2 different loci (each tree from one single locus). I know that the trees were obtained from the same organisms, but I don't know the correspondence between the tips of the trees. That means that the trees can be considered as unlabeled or having different labels.

What I want to figure out, is a way to match tips from one tree with tips from the other tree so that in the end I get as close as possible of having sets of 2 tips each, one from one tree and one from the other that are from the same species, meaning that by comparing the trees in some way I could match sequences from different loci without knowing their order or having a common labeling.

Imagine that this represents the tips of the trees:

species1_locusA    species4_locusB
species4_locusA    species1_locusB
species2_locusA    species3_locusB
species3_locusA    species2_locusB

I only know that one tree is from locus A of 4 species and the other tree is from locus B of the same species. They don't have labels or have different labels so I can't match things by labels. Due to tree discordance and use of different loci, the trees won't match in terms of topology but might have some similarities.

Does anyone know a way to start looking into this or know some research that might help? As far as I've seen, most programs need trees with the same labels or a correspondence between labels.

Thanks in advance for any help.

[Jean-Karim Heriche]

It seems like a graph matching problem to me.

[rfm]

Thanks for the suggestion. I don't know much about graphs but I'll definitely look into that to see if it helps.

[Selenocysteine]

Do you actually know the species corresponding to each tip on each tree, or are they unknown?

[rfm]

I don't know the species corresponding to each tip. I only know that the tree is from one locus and that the group and number of species in both trees should be the same. Identity of tips is uncertain. I don't know if I can somewhat identify signals in the trees topologies that can actually help.