I've no idea what a "consensus path" is so the following code, while fun to write, is probably wildly wide of what you want to achieve. It may act as a starting point for discussion though.

#!/usr/bin/perl -l
use strict;
use warnings;

my @paths;

push @paths, [map {chomp; $_} split /\s*:\s*/] while <DATA>;

my @pattern = @{pop @paths};

for my $part (@pattern) {
    my ($node, $dir) = split '', $part;

    for my $testPattern (@paths) {
        if ($dir eq '+') {
            next if $testPattern->[0] !~ $node;
            $part = $testPattern;
            last;
        } else {
            next if $testPattern->[-1] !~ $node;
            $part = [map {tr~+-~-+~; $_} reverse @$testPattern];
            last;
        }
    }
    
    die "Can't match $part in '@pattern'\n" if 'ARRAY' ne ref $part;
}

print join ' : ', map {@$_} @pattern;

__DATA__
A+ : B+
C+ : D- : E-
C+ : E-
[download]

Prints:

C- : D+ : E+ : E+ : D+ : C-
[download]