| 1 | package App::Dazz::Command::layout; | ||||||||||||||||||||||||||||||||
| 2 | 11 | ▶ | use strict; | ||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||
| 3 | 11 | ▶ | use warnings; | ||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||
| 4 | 11 | ▶ | use autodie; | ||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||
| 5 | |||||||||||||||||||||||||||||||||
| 6 | 11 | ▶ | use App::Dazz -command; | ||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||
| 7 | 11 | ▶ | use App::Dazz::Common; | ||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||
| 8 | |||||||||||||||||||||||||||||||||
| 9 | 2 | ▶ | sub abstract { | ||||||||||||||||||||||||||||||
|
Subroutine
abstract: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||
| 10 | 2 | return 'layout anchors within a group'; | |||||||||||||||||||||||||||||||
| 11 | } | ||||||||||||||||||||||||||||||||
| 12 | |||||||||||||||||||||||||||||||||
| 13 | 5 | ▶ | sub opt_spec { | ||||||||||||||||||||||||||||||
|
Subroutine
opt_spec: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||
| 14 | return ( | ||||||||||||||||||||||||||||||||
| 15 | 5 | [ "outfile|o=s", "output filename", ], | |||||||||||||||||||||||||||||||
| 16 | [ 'border=i', 'length of borders in anchors', { default => 500 }, ], | ||||||||||||||||||||||||||||||||
| 17 | [ "max=i", "max distance", { default => 5000 }, ], | ||||||||||||||||||||||||||||||||
| 18 | [ 'pa=s', 'prefix of anchors', { default => "anchor" }, ], | ||||||||||||||||||||||||||||||||
| 19 | [ 'oa=s', 'overlaps between anchors', ], | ||||||||||||||||||||||||||||||||
| 20 | [ "png", "write a png file via graphviz", ], | ||||||||||||||||||||||||||||||||
| 21 | { show_defaults => 1, }, | ||||||||||||||||||||||||||||||||
| 22 | ); | ||||||||||||||||||||||||||||||||
| 23 | } | ||||||||||||||||||||||||||||||||
| 24 | |||||||||||||||||||||||||||||||||
| 25 | 5 | ▶ | sub usage_desc { | ||||||||||||||||||||||||||||||
|
Subroutine
usage_desc: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||
| 26 | 5 | return "dazz layout [options] <strand.fasta> <.ovlp.tsv> <.relation.tsv>"; | |||||||||||||||||||||||||||||||
| 27 | } | ||||||||||||||||||||||||||||||||
| 28 | |||||||||||||||||||||||||||||||||
| 29 | 1 | ▶ | sub description { | ||||||||||||||||||||||||||||||
|
Subroutine
description: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||
| 30 | 1 | my $desc; | |||||||||||||||||||||||||||||||
| 31 | 1 | $desc .= ucfirst(abstract) . ".\n"; | |||||||||||||||||||||||||||||||
| 32 | 1 | return $desc; | |||||||||||||||||||||||||||||||
| 33 | } | ||||||||||||||||||||||||||||||||
| 34 | |||||||||||||||||||||||||||||||||
| 35 | 4 | ▶ | sub validate_args { | ||||||||||||||||||||||||||||||
|
Subroutine
validate_args: called CC=8 SCAR=21.3
Pod
documented
| |||||||||||||||||||||||||||||||||
| 36 | 4 | my ( $self, $opt, $args ) = @_; | |||||||||||||||||||||||||||||||
| 37 | |||||||||||||||||||||||||||||||||
| 38 | 4 | ▶ | if ( @{$args} != 3 ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 39 | 2 | my $message = "This command need three input files.\n\tIt found"; | |||||||||||||||||||||||||||||||
| 40 | 2 | $message .= sprintf " [%s]", $_ for @{$args}; | |||||||||||||||||||||||||||||||
| 41 | 2 | $message .= ".\n"; | |||||||||||||||||||||||||||||||
| 42 | 2 | $self->usage_error($message); | |||||||||||||||||||||||||||||||
| 43 | } | ||||||||||||||||||||||||||||||||
| 44 | 2 | for ( @{$args} ) { | |||||||||||||||||||||||||||||||
| 45 | 4 | ▶ | if ( !Path::Tiny::path($_)->is_file ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 46 | 1 | $self->usage_error("The input file [$_] doesn't exist."); | |||||||||||||||||||||||||||||||
| 47 | } | ||||||||||||||||||||||||||||||||
| 48 | } | ||||||||||||||||||||||||||||||||
| 49 | |||||||||||||||||||||||||||||||||
| 50 | 1 | ▶ | if ( $opt->{oa} ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 51 | 1 | ▶ | if ( !Path::Tiny::path( $opt->{oa} )->is_file ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 52 | 0 | $self->usage_error("The overlap file [$opt->{oa}] doesn't exist.\n"); | |||||||||||||||||||||||||||||||
| 53 | } | ||||||||||||||||||||||||||||||||
| 54 | } | ||||||||||||||||||||||||||||||||
| 55 | |||||||||||||||||||||||||||||||||
| 56 | 1 | ▶ | if ( !exists $opt->{outfile} ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 57 | 0 | $opt->{outfile} = Path::Tiny::path( $args->[1] )->absolute . ".contig.fasta"; | |||||||||||||||||||||||||||||||
| 58 | } | ||||||||||||||||||||||||||||||||
| 59 | } | ||||||||||||||||||||||||||||||||
| 60 | |||||||||||||||||||||||||||||||||
| 61 | 1 | ▶ | sub execute { | ||||||||||||||||||||||||||||||
|
Subroutine
execute: called CC=63 SCAR=59.2
Pod
documented
| |||||||||||||||||||||||||||||||||
| 62 | 1 | my ( $self, $opt, $args ) = @_; | |||||||||||||||||||||||||||||||
| 63 | |||||||||||||||||||||||||||||||||
| 64 | #----------------------------# | ||||||||||||||||||||||||||||||||
| 65 | # loading sequences | ||||||||||||||||||||||||||||||||
| 66 | #----------------------------# | ||||||||||||||||||||||||||||||||
| 67 | 1 | my $seq_of = App::Fasops::Common::read_fasta( $args->[0] ); | |||||||||||||||||||||||||||||||
| 68 | 1 | my %is_anchor; | |||||||||||||||||||||||||||||||
| 69 | 1 | for my $id ( keys %{$seq_of} ) { | |||||||||||||||||||||||||||||||
| 70 | 23 | ▶ | if ( index( $id, $opt->{pa} . "/" ) == 0 ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 71 | 4 | $is_anchor{$id} = 1; | |||||||||||||||||||||||||||||||
| 72 | } | ||||||||||||||||||||||||||||||||
| 73 | } | ||||||||||||||||||||||||||||||||
| 74 | |||||||||||||||||||||||||||||||||
| 75 | #----------------------------# | ||||||||||||||||||||||||||||||||
| 76 | # load overlaps and build graph | ||||||||||||||||||||||||||||||||
| 77 | #----------------------------# | ||||||||||||||||||||||||||||||||
| 78 | 1 | my $graph = Graph->new( directed => 1 ); | |||||||||||||||||||||||||||||||
| 79 | 1 | my $links_of = {}; # long_id => { anchor_id => overlap_on_long, } | |||||||||||||||||||||||||||||||
| 80 | { | ||||||||||||||||||||||||||||||||
| 81 | 1 | open my $in_fh, "<", $args->[1]; | |||||||||||||||||||||||||||||||
| 82 | |||||||||||||||||||||||||||||||||
| 83 | 1 | my %seen_pair; | |||||||||||||||||||||||||||||||
| 84 | 1 | ▶ | while ( my $line = <$in_fh> ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 85 | 102 | my $info = App::Dazz::Common::parse_ovlp_line($line); | |||||||||||||||||||||||||||||||
| 86 | |||||||||||||||||||||||||||||||||
| 87 | # ignore self overlapping | ||||||||||||||||||||||||||||||||
| 88 | 102 | ▶ | next if $info->{f_id} eq $info->{g_id}; | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 89 | |||||||||||||||||||||||||||||||||
| 90 | # we've orient all sequences to the same strand | ||||||||||||||||||||||||||||||||
| 91 | 102 | ▶ | next if $info->{g_strand} == 1; | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 92 | |||||||||||||||||||||||||||||||||
| 93 | # skip duplicated overlaps | ||||||||||||||||||||||||||||||||
| 94 | 102 | my $pair = join( "-", sort ( $info->{f_id}, $info->{g_id} ) ); | |||||||||||||||||||||||||||||||
| 95 | 102 | ▶ | next if $seen_pair{$pair}; | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 96 | 51 | $seen_pair{$pair}++; | |||||||||||||||||||||||||||||||
| 97 | |||||||||||||||||||||||||||||||||
| 98 | 51 | ▶ | if ( $info->{f_B} > 0 ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 99 | 7 | ▶ | if ( $info->{f_E} == $info->{f_len} ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 100 | |||||||||||||||||||||||||||||||||
| 101 | # f.B f.E | ||||||||||||||||||||||||||||||||
| 102 | # f ========+----------> | ||||||||||||||||||||||||||||||||
| 103 | # g -----------+=======> | ||||||||||||||||||||||||||||||||
| 104 | # g.B g.E | ||||||||||||||||||||||||||||||||
| 105 | $graph->add_weighted_edge( $info->{f_id}, $info->{g_id}, | ||||||||||||||||||||||||||||||||
| 106 | 7 | $info->{g_len} - $info->{g_E} ); | |||||||||||||||||||||||||||||||
| 107 | } | ||||||||||||||||||||||||||||||||
| 108 | else { | ||||||||||||||||||||||||||||||||
| 109 | # f.B f.E | ||||||||||||||||||||||||||||||||
| 110 | # f ========+----------+=======> | ||||||||||||||||||||||||||||||||
| 111 | # g -----------> | ||||||||||||||||||||||||||||||||
| 112 | # g.B g.E | ||||||||||||||||||||||||||||||||
| 113 | $graph->add_weighted_edge( $info->{g_id}, $info->{f_id}, | ||||||||||||||||||||||||||||||||
| 114 | 0 | $info->{f_len} - $info->{f_E} ); | |||||||||||||||||||||||||||||||
| 115 | } | ||||||||||||||||||||||||||||||||
| 116 | } | ||||||||||||||||||||||||||||||||
| 117 | else { | ||||||||||||||||||||||||||||||||
| 118 | 44 | ▶ | if ( $info->{g_E} == $info->{g_len} ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 119 | |||||||||||||||||||||||||||||||||
| 120 | # f.B f.E | ||||||||||||||||||||||||||||||||
| 121 | # f -----------+=======> | ||||||||||||||||||||||||||||||||
| 122 | # g ========+----------> | ||||||||||||||||||||||||||||||||
| 123 | # g.B g.E | ||||||||||||||||||||||||||||||||
| 124 | $graph->add_weighted_edge( $info->{g_id}, $info->{f_id}, | ||||||||||||||||||||||||||||||||
| 125 | 5 | $info->{f_len} - $info->{f_E} ); | |||||||||||||||||||||||||||||||
| 126 | } | ||||||||||||||||||||||||||||||||
| 127 | else { | ||||||||||||||||||||||||||||||||
| 128 | # f.B f.E | ||||||||||||||||||||||||||||||||
| 129 | # f -----------> | ||||||||||||||||||||||||||||||||
| 130 | # g ========+----------+=======> | ||||||||||||||||||||||||||||||||
| 131 | # g.B g.E | ||||||||||||||||||||||||||||||||
| 132 | $graph->add_weighted_edge( $info->{f_id}, $info->{g_id}, | ||||||||||||||||||||||||||||||||
| 133 | 39 | $info->{g_len} - $info->{g_E} ); | |||||||||||||||||||||||||||||||
| 134 | } | ||||||||||||||||||||||||||||||||
| 135 | } | ||||||||||||||||||||||||||||||||
| 136 | |||||||||||||||||||||||||||||||||
| 137 | 51 | ▶ | if ( $is_anchor{ $info->{f_id} } and !$is_anchor{ $info->{g_id} } ) { | ||||||||||||||||||||||||||||||
|
Branch: 2 branches
Condition33%1/3
$is_anchor{$info->{"f_id"}} and not $is_anchor{$info->{"g_id"}}
MC/DC0%0/2
$is_anchor{$info->{"f_id"}} and not $is_anchor{$info->{"g_id"}}
$is_anchor{$info->{"f_id"}}
not $is_anchor{$info->{"g_id"}}
Truth table33%1/3
A and not(B)
A= $is_anchor{$info->{"f_id"}}B= not $is_anchor{$info->{"g_id"}}
| |||||||||||||||||||||||||||||||||
| 138 | 51 | my ( $beg, $end ) = App::Dazz::Common::beg_end( $info->{g_B}, $info->{g_E}, ); | |||||||||||||||||||||||||||||||
| 139 | $links_of->{ $info->{g_id} }{ $info->{f_id} } | ||||||||||||||||||||||||||||||||
| 140 | 51 | = AlignDB::IntSpan->new->add_pair( $beg, $end ); | |||||||||||||||||||||||||||||||
| 141 | } | ||||||||||||||||||||||||||||||||
| 142 | ▶ | elsif ( $is_anchor{ $info->{g_id} } and !$is_anchor{ $info->{f_id} } ) { | |||||||||||||||||||||||||||||||
|
Condition0%0/3
$is_anchor{$info->{"g_id"}} and not $is_anchor{$info->{"f_id"}}
MC/DC0%0/2
$is_anchor{$info->{"g_id"}} and not $is_anchor{$info->{"f_id"}}
$is_anchor{$info->{"g_id"}}
not $is_anchor{$info->{"f_id"}}
Truth table0%0/3
A and not(B)
A= $is_anchor{$info->{"g_id"}}B= not $is_anchor{$info->{"f_id"}}
| |||||||||||||||||||||||||||||||||
| 143 | 0 | my ( $beg, $end ) = App::Dazz::Common::beg_end( $info->{f_B}, $info->{f_E}, ); | |||||||||||||||||||||||||||||||
| 144 | $links_of->{ $info->{f_id} }{ $info->{g_id} } | ||||||||||||||||||||||||||||||||
| 145 | 0 | = AlignDB::IntSpan->new->add_pair( $beg, $end ); | |||||||||||||||||||||||||||||||
| 146 | } | ||||||||||||||||||||||||||||||||
| 147 | } | ||||||||||||||||||||||||||||||||
| 148 | 1 | close $in_fh; | |||||||||||||||||||||||||||||||
| 149 | } | ||||||||||||||||||||||||||||||||
| 150 | 1 | ▶ | if ( $opt->{png} ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 151 | 0 | App::Dazz::Common::g2gv( $graph, $args->[1] . ".linker.png" ); | |||||||||||||||||||||||||||||||
| 152 | } | ||||||||||||||||||||||||||||||||
| 153 | |||||||||||||||||||||||||||||||||
| 154 | #----------------------------# | ||||||||||||||||||||||||||||||||
| 155 | # Graph of anchors | ||||||||||||||||||||||||||||||||
| 156 | #----------------------------# | ||||||||||||||||||||||||||||||||
| 157 | 1 | my $anchor_graph = Graph->new( directed => 1 ); | |||||||||||||||||||||||||||||||
| 158 | { | ||||||||||||||||||||||||||||||||
| 159 | 1 | my @nodes = $graph->vertices; | |||||||||||||||||||||||||||||||
| 160 | 1 | my @linkers = grep { !$is_anchor{$_} } @nodes; | |||||||||||||||||||||||||||||||
| 161 | |||||||||||||||||||||||||||||||||
| 162 | 1 | for my $l (@linkers) { | |||||||||||||||||||||||||||||||
| 163 | 19 | my @p = grep { $is_anchor{$_} } $graph->predecessors($l); | |||||||||||||||||||||||||||||||
| 164 | 19 | my @s = grep { $is_anchor{$_} } $graph->successors($l); | |||||||||||||||||||||||||||||||
| 165 | |||||||||||||||||||||||||||||||||
| 166 | 19 | for my $p (@p) { | |||||||||||||||||||||||||||||||
| 167 | 46 | for my $s (@s) { | |||||||||||||||||||||||||||||||
| 168 | 9 | $anchor_graph->add_edge( $p, $s ); | |||||||||||||||||||||||||||||||
| 169 | } | ||||||||||||||||||||||||||||||||
| 170 | } | ||||||||||||||||||||||||||||||||
| 171 | |||||||||||||||||||||||||||||||||
| 172 | 19 | ▶ | if ( @p > 1 ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 173 | 44 | @p = map { $_->[0] } | |||||||||||||||||||||||||||||||
| 174 | 34 | sort { $b->[1] <=> $a->[1] } | |||||||||||||||||||||||||||||||
| 175 | 17 | map { [ $_, $graph->get_edge_weight( $_, $l ) ] } @p; | |||||||||||||||||||||||||||||||
| 176 | 17 | for my $i ( 0 .. $#p - 1 ) { | |||||||||||||||||||||||||||||||
| 177 | 27 | $anchor_graph->add_edge( $p[$i], $p[ $i + 1 ] ); | |||||||||||||||||||||||||||||||
| 178 | } | ||||||||||||||||||||||||||||||||
| 179 | } | ||||||||||||||||||||||||||||||||
| 180 | |||||||||||||||||||||||||||||||||
| 181 | 19 | ▶ | if ( @s > 1 ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 182 | 0 | @s = map { $_->[0] } | |||||||||||||||||||||||||||||||
| 183 | 0 | sort { $a->[1] <=> $b->[1] } | |||||||||||||||||||||||||||||||
| 184 | 0 | map { [ $_, $graph->get_edge_weight( $l, $_, ) ] } @s; | |||||||||||||||||||||||||||||||
| 185 | 0 | for my $i ( 0 .. $#s - 1 ) { | |||||||||||||||||||||||||||||||
| 186 | 0 | $anchor_graph->add_edge( $s[$i], $s[ $i + 1 ] ); | |||||||||||||||||||||||||||||||
| 187 | } | ||||||||||||||||||||||||||||||||
| 188 | } | ||||||||||||||||||||||||||||||||
| 189 | } | ||||||||||||||||||||||||||||||||
| 190 | |||||||||||||||||||||||||||||||||
| 191 | # add anchors missed in $anchor_graph, i.e., not correctly linked to long.fasta | ||||||||||||||||||||||||||||||||
| 192 | 1 | for my $id ( keys %is_anchor ) { | |||||||||||||||||||||||||||||||
| 193 | 4 | ▶ | if ( !$anchor_graph->has_vertex($id) ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 194 | 0 | $anchor_graph->add_vertex($id); | |||||||||||||||||||||||||||||||
| 195 | } | ||||||||||||||||||||||||||||||||
| 196 | } | ||||||||||||||||||||||||||||||||
| 197 | |||||||||||||||||||||||||||||||||
| 198 | 1 | ▶ | if ( $opt->{png} ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 199 | 0 | App::Dazz::Common::g2gv( $anchor_graph, $args->[1] . ".png" ); | |||||||||||||||||||||||||||||||
| 200 | } | ||||||||||||||||||||||||||||||||
| 201 | 1 | App::Dazz::Common::transitive_reduction($anchor_graph); | |||||||||||||||||||||||||||||||
| 202 | 1 | ▶ | if ( $opt->{png} ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 203 | 0 | App::Dazz::Common::g2gv( $anchor_graph, $args->[1] . ".reduced.png" ); | |||||||||||||||||||||||||||||||
| 204 | } | ||||||||||||||||||||||||||||||||
| 205 | } | ||||||||||||||||||||||||||||||||
| 206 | |||||||||||||||||||||||||||||||||
| 207 | #----------------------------# | ||||||||||||||||||||||||||||||||
| 208 | # existing relations | ||||||||||||||||||||||||||||||||
| 209 | #----------------------------# | ||||||||||||||||||||||||||||||||
| 210 | 1 | my $relation_of = {}; | |||||||||||||||||||||||||||||||
| 211 | { | ||||||||||||||||||||||||||||||||
| 212 | 1 | for my $line ( Path::Tiny::path( $args->[2] )->lines( { chomp => 1 } ) ) { | |||||||||||||||||||||||||||||||
| 213 | 3 | my @fields = split "\t", $line; | |||||||||||||||||||||||||||||||
| 214 | |||||||||||||||||||||||||||||||||
| 215 | 3 | my $anchor_0 = $fields[0]; | |||||||||||||||||||||||||||||||
| 216 | 3 | my $anchor_1 = $fields[1]; | |||||||||||||||||||||||||||||||
| 217 | 3 | my @distances = split ",", $fields[2]; | |||||||||||||||||||||||||||||||
| 218 | 3 | my @long_reads = split ",", $fields[3]; | |||||||||||||||||||||||||||||||
| 219 | |||||||||||||||||||||||||||||||||
| 220 | 3 | my $pair = join "-", sort ( $anchor_0, $anchor_1, ); | |||||||||||||||||||||||||||||||
| 221 | 3 | $relation_of->{$pair} = { | |||||||||||||||||||||||||||||||
| 222 | distances => \@distances, | ||||||||||||||||||||||||||||||||
| 223 | long_reads => \@long_reads, | ||||||||||||||||||||||||||||||||
| 224 | }; | ||||||||||||||||||||||||||||||||
| 225 | } | ||||||||||||||||||||||||||||||||
| 226 | } | ||||||||||||||||||||||||||||||||
| 227 | |||||||||||||||||||||||||||||||||
| 228 | #----------------------------# | ||||||||||||||||||||||||||||||||
| 229 | # link anchors and break branches | ||||||||||||||||||||||||||||||||
| 230 | #----------------------------# | ||||||||||||||||||||||||||||||||
| 231 | 1 | my @paths; | |||||||||||||||||||||||||||||||
| 232 | 1 | ▶ | if ( $anchor_graph->is_dag ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 233 | 1 | ▶ | if ( scalar $anchor_graph->exterior_vertices == 2 ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 234 | 1 | print STDERR " Linear\n"; | |||||||||||||||||||||||||||||||
| 235 | |||||||||||||||||||||||||||||||||
| 236 | 1 | my @ts = $anchor_graph->topological_sort; | |||||||||||||||||||||||||||||||
| 237 | |||||||||||||||||||||||||||||||||
| 238 | 1 | my %idx_of; | |||||||||||||||||||||||||||||||
| 239 | 1 | for my $idx ( 0 .. $#ts ) { | |||||||||||||||||||||||||||||||
| 240 | 4 | $idx_of{ $ts[$idx] } = $idx; | |||||||||||||||||||||||||||||||
| 241 | } | ||||||||||||||||||||||||||||||||
| 242 | 1 | for my $wcc ( $anchor_graph->weakly_connected_components ) { | |||||||||||||||||||||||||||||||
| 243 | 4 | my @cc = map { $_->[0] } | |||||||||||||||||||||||||||||||
| 244 | 4 | sort { $a->[1] <=> $b->[1] } | |||||||||||||||||||||||||||||||
| 245 | 1 | map { [ $_, $idx_of{$_} ] } @{$wcc}; | |||||||||||||||||||||||||||||||
| 246 | |||||||||||||||||||||||||||||||||
| 247 | 1 | push @paths, \@cc; | |||||||||||||||||||||||||||||||
| 248 | } | ||||||||||||||||||||||||||||||||
| 249 | } | ||||||||||||||||||||||||||||||||
| 250 | else { | ||||||||||||||||||||||||||||||||
| 251 | 0 | print STDERR " Branched\n"; | |||||||||||||||||||||||||||||||
| 252 | |||||||||||||||||||||||||||||||||
| 253 | 0 | my @ts = $anchor_graph->topological_sort; | |||||||||||||||||||||||||||||||
| 254 | |||||||||||||||||||||||||||||||||
| 255 | 0 | my @branchings; | |||||||||||||||||||||||||||||||
| 256 | my %idx_of; | ||||||||||||||||||||||||||||||||
| 257 | 0 | for my $idx ( 0 .. $#ts ) { | |||||||||||||||||||||||||||||||
| 258 | 0 | $idx_of{ $ts[$idx] } = $idx; | |||||||||||||||||||||||||||||||
| 259 | |||||||||||||||||||||||||||||||||
| 260 | 0 | ▶ | if ( $anchor_graph->out_degree( $ts[$idx] ) > 1 | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition0%0/3
$anchor_graph->out_degree($ts[$idx]) > 1 or $anchor_graph->in_degree($ts[$idx]) > 1
MC/DC0%0/2
$anchor_graph->out_degree($ts[$idx]) > 1 or $anchor_graph->in_degree($ts[$idx]) > 1
$anchor_graph->out_degree($ts[$idx]) > 1
$anchor_graph->in_degree($ts[$idx]) > 1
Truth table0%0/3
A or B
A= $anchor_graph->out_degree($ts[$idx]) > 1B= $anchor_graph->in_degree($ts[$idx]) > 1
| |||||||||||||||||||||||||||||||||
| 261 | or $anchor_graph->in_degree( $ts[$idx] ) > 1 ) | ||||||||||||||||||||||||||||||||
| 262 | { | ||||||||||||||||||||||||||||||||
| 263 | 0 | push @branchings, $ts[$idx]; | |||||||||||||||||||||||||||||||
| 264 | } | ||||||||||||||||||||||||||||||||
| 265 | } | ||||||||||||||||||||||||||||||||
| 266 | |||||||||||||||||||||||||||||||||
| 267 | 0 | $anchor_graph->delete_vertex($_) for @branchings; | |||||||||||||||||||||||||||||||
| 268 | |||||||||||||||||||||||||||||||||
| 269 | 0 | for my $wcc ( $anchor_graph->weakly_connected_components ) { | |||||||||||||||||||||||||||||||
| 270 | 0 | my @cc = map { $_->[0] } | |||||||||||||||||||||||||||||||
| 271 | 0 | sort { $a->[1] <=> $b->[1] } | |||||||||||||||||||||||||||||||
| 272 | 0 | map { [ $_, $idx_of{$_} ] } @{$wcc}; | |||||||||||||||||||||||||||||||
| 273 | |||||||||||||||||||||||||||||||||
| 274 | 0 | push @paths, \@cc; | |||||||||||||||||||||||||||||||
| 275 | } | ||||||||||||||||||||||||||||||||
| 276 | |||||||||||||||||||||||||||||||||
| 277 | # standalone branching nodes | ||||||||||||||||||||||||||||||||
| 278 | 0 | push @paths, [$_] for @branchings; | |||||||||||||||||||||||||||||||
| 279 | } | ||||||||||||||||||||||||||||||||
| 280 | } | ||||||||||||||||||||||||||||||||
| 281 | else { | ||||||||||||||||||||||||||||||||
| 282 | 0 | print STDERR " Cyclic\n"; | |||||||||||||||||||||||||||||||
| 283 | 0 | ▶ | while ( $anchor_graph->has_a_cycle ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 284 | 0 | my @cycles = $anchor_graph->find_a_cycle; | |||||||||||||||||||||||||||||||
| 285 | 0 | $anchor_graph->delete_vertex($_) for @cycles; | |||||||||||||||||||||||||||||||
| 286 | 0 | push @paths, [$_] for @cycles; | |||||||||||||||||||||||||||||||
| 287 | } | ||||||||||||||||||||||||||||||||
| 288 | |||||||||||||||||||||||||||||||||
| 289 | 0 | ▶ | if ( scalar $anchor_graph->vertices ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 290 | 0 | my @ts = $anchor_graph->topological_sort; | |||||||||||||||||||||||||||||||
| 291 | 0 | my %idx_of; | |||||||||||||||||||||||||||||||
| 292 | 0 | for my $idx ( 0 .. $#ts ) { | |||||||||||||||||||||||||||||||
| 293 | 0 | $idx_of{ $ts[$idx] } = $idx; | |||||||||||||||||||||||||||||||
| 294 | } | ||||||||||||||||||||||||||||||||
| 295 | |||||||||||||||||||||||||||||||||
| 296 | 0 | for my $wcc ( $anchor_graph->weakly_connected_components ) { | |||||||||||||||||||||||||||||||
| 297 | 0 | my @cc = map { $_->[0] } | |||||||||||||||||||||||||||||||
| 298 | 0 | sort { $a->[1] <=> $b->[1] } | |||||||||||||||||||||||||||||||
| 299 | 0 | map { [ $_, $idx_of{$_} ] } @{$wcc}; | |||||||||||||||||||||||||||||||
| 300 | |||||||||||||||||||||||||||||||||
| 301 | 0 | push @paths, \@cc; | |||||||||||||||||||||||||||||||
| 302 | } | ||||||||||||||||||||||||||||||||
| 303 | } | ||||||||||||||||||||||||||||||||
| 304 | } | ||||||||||||||||||||||||||||||||
| 305 | 1 | Path::Tiny::path( $opt->{outfile} . ".paths.yml" )->spew( YAML::Syck::Dump( \@paths ) ); | |||||||||||||||||||||||||||||||
| 306 | |||||||||||||||||||||||||||||||||
| 307 | #----------------------------# | ||||||||||||||||||||||||||||||||
| 308 | # existing overlaps | ||||||||||||||||||||||||||||||||
| 309 | #----------------------------# | ||||||||||||||||||||||||||||||||
| 310 | 1 | my $existing_ovlp_of = {}; | |||||||||||||||||||||||||||||||
| 311 | 1 | ▶ | if ( $opt->{oa} ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 312 | 1 | open my $in_fh, "<", $opt->{oa}; | |||||||||||||||||||||||||||||||
| 313 | |||||||||||||||||||||||||||||||||
| 314 | 1 | ▶ | while ( my $line = <$in_fh> ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 315 | 1 | my $info = App::Dazz::Common::parse_ovlp_line($line); | |||||||||||||||||||||||||||||||
| 316 | |||||||||||||||||||||||||||||||||
| 317 | # ignore self overlapping | ||||||||||||||||||||||||||||||||
| 318 | 1 | ▶ | next if $info->{f_id} eq $info->{g_id}; | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 319 | |||||||||||||||||||||||||||||||||
| 320 | # we've orient all sequences to the same strand | ||||||||||||||||||||||||||||||||
| 321 | 1 | ▶ | next if $info->{g_strand} == 1; | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 322 | |||||||||||||||||||||||||||||||||
| 323 | 1 | my $pair = join( "-", sort ( $info->{f_id}, $info->{g_id} ) ); | |||||||||||||||||||||||||||||||
| 324 | |||||||||||||||||||||||||||||||||
| 325 | 1 | $existing_ovlp_of->{$pair} = $info; | |||||||||||||||||||||||||||||||
| 326 | } | ||||||||||||||||||||||||||||||||
| 327 | 1 | close $in_fh; | |||||||||||||||||||||||||||||||
| 328 | } | ||||||||||||||||||||||||||||||||
| 329 | |||||||||||||||||||||||||||||||||
| 330 | 1 | my $basename = Path::Tiny::path( $opt->{outfile} )->basename(); | |||||||||||||||||||||||||||||||
| 331 | 1 | ($basename) = split /\./, $basename; | |||||||||||||||||||||||||||||||
| 332 | 1 | my $contig; | |||||||||||||||||||||||||||||||
| 333 | 1 | my $count = 1; | |||||||||||||||||||||||||||||||
| 334 | 1 | for my $i ( 0 .. $#paths ) { | |||||||||||||||||||||||||||||||
| 335 | 1 | $contig .= sprintf ">%s_%d\n", $basename, $count; | |||||||||||||||||||||||||||||||
| 336 | |||||||||||||||||||||||||||||||||
| 337 | 1 | my @nodes = @{ $paths[$i] }; | |||||||||||||||||||||||||||||||
| 338 | |||||||||||||||||||||||||||||||||
| 339 | 1 | ▶ | if ( @nodes == 1 ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 340 | 0 | $contig .= $seq_of->{ $nodes[0] }; | |||||||||||||||||||||||||||||||
| 341 | 0 | $contig .= "\n"; | |||||||||||||||||||||||||||||||
| 342 | 0 | $count++; | |||||||||||||||||||||||||||||||
| 343 | 0 | next; | |||||||||||||||||||||||||||||||
| 344 | } | ||||||||||||||||||||||||||||||||
| 345 | |||||||||||||||||||||||||||||||||
| 346 | 1 | my $flag_start = 1; | |||||||||||||||||||||||||||||||
| 347 | 1 | for my $j ( 0 .. $#nodes - 1 ) { | |||||||||||||||||||||||||||||||
| 348 | 3 | my $anchor_0 = $nodes[$j]; | |||||||||||||||||||||||||||||||
| 349 | 3 | my $anchor_1 = $nodes[ $j + 1 ]; | |||||||||||||||||||||||||||||||
| 350 | 3 | my $pair = join "-", sort ( $anchor_0, $anchor_1, ); | |||||||||||||||||||||||||||||||
| 351 | |||||||||||||||||||||||||||||||||
| 352 | 3 | ▶ | if ($flag_start) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 353 | 1 | $contig .= $seq_of->{$anchor_0}; | |||||||||||||||||||||||||||||||
| 354 | 1 | $flag_start = 0; | |||||||||||||||||||||||||||||||
| 355 | } | ||||||||||||||||||||||||||||||||
| 356 | |||||||||||||||||||||||||||||||||
| 357 | 3 | ▶ | if ( !exists $relation_of->{$pair} ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 358 | 0 | print STDERR " No reliable links between $pair\n"; | |||||||||||||||||||||||||||||||
| 359 | 0 | $count++; | |||||||||||||||||||||||||||||||
| 360 | 0 | $contig .= "\n"; | |||||||||||||||||||||||||||||||
| 361 | 0 | $contig .= sprintf ">%s_%d\n", $basename, $count; | |||||||||||||||||||||||||||||||
| 362 | 0 | ▶ | if ( $j == $#nodes - 1 ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 363 | 0 | $contig .= $seq_of->{$anchor_1}; | |||||||||||||||||||||||||||||||
| 364 | } | ||||||||||||||||||||||||||||||||
| 365 | |||||||||||||||||||||||||||||||||
| 366 | 0 | $flag_start = 1; | |||||||||||||||||||||||||||||||
| 367 | 0 | next; | |||||||||||||||||||||||||||||||
| 368 | } | ||||||||||||||||||||||||||||||||
| 369 | |||||||||||||||||||||||||||||||||
| 370 | 3 | my $seq_anchor_1 = $seq_of->{$anchor_1}; | |||||||||||||||||||||||||||||||
| 371 | |||||||||||||||||||||||||||||||||
| 372 | 3 | ▶ | if ( $existing_ovlp_of->{$pair} ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 373 | 1 | my $ovlp_len = $existing_ovlp_of->{$pair}{ovlp_len}; | |||||||||||||||||||||||||||||||
| 374 | 1 | $contig .= substr $seq_anchor_1, $ovlp_len; | |||||||||||||||||||||||||||||||
| 375 | } | ||||||||||||||||||||||||||||||||
| 376 | else { | ||||||||||||||||||||||||||||||||
| 377 | my $avg_distance | ||||||||||||||||||||||||||||||||
| 378 | 2 | = int App::Fasops::Common::mean( @{ $relation_of->{$pair}{distances} } ); | |||||||||||||||||||||||||||||||
| 379 | |||||||||||||||||||||||||||||||||
| 380 | 2 | ▶ | if ( $avg_distance < 0 ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 381 | 2 | ▶ | if ( abs($avg_distance) < 5 ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 382 | 0 | $contig .= substr $seq_anchor_1, abs($avg_distance); | |||||||||||||||||||||||||||||||
| 383 | } | ||||||||||||||||||||||||||||||||
| 384 | else { | ||||||||||||||||||||||||||||||||
| 385 | 2 | my $ovlp_len_120 = int( abs($avg_distance) * 1.2 ); | |||||||||||||||||||||||||||||||
| 386 | 2 | my $ovlp_seq_contig = substr $contig, -$ovlp_len_120; | |||||||||||||||||||||||||||||||
| 387 | 2 | my $ovlp_seq_anchor_1 = substr $seq_anchor_1, 0, $ovlp_len_120; | |||||||||||||||||||||||||||||||
| 388 | |||||||||||||||||||||||||||||||||
| 389 | 2 | my $ovlp_seq; | |||||||||||||||||||||||||||||||
| 390 | 2 | ▶ | if ( abs($avg_distance) < 30 ) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 391 | |||||||||||||||||||||||||||||||||
| 392 | # abs($avg_distance) should be less than 30. | ||||||||||||||||||||||||||||||||
| 393 | # Larger overlaps have been detected by daligner (--oa) | ||||||||||||||||||||||||||||||||
| 394 | 1 | my ( $lcss, $offset_contig, $offset_anchor_1 ) | |||||||||||||||||||||||||||||||
| 395 | = App::Dazz::Common::lcss( $ovlp_seq_contig, $ovlp_seq_anchor_1 ); | ||||||||||||||||||||||||||||||||
| 396 | |||||||||||||||||||||||||||||||||
| 397 | 1 | ▶ | if ($lcss) { | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 398 | |||||||||||||||||||||||||||||||||
| 399 | # build overlap sequences | ||||||||||||||||||||||||||||||||
| 400 | 1 | substr $ovlp_seq_contig, $offset_contig, length($lcss), ""; | |||||||||||||||||||||||||||||||
| 401 | 1 | substr $ovlp_seq_anchor_1, $offset_anchor_1, length($lcss), ""; | |||||||||||||||||||||||||||||||
| 402 | 1 | $ovlp_seq = $ovlp_seq_contig . $lcss . $ovlp_seq_anchor_1; | |||||||||||||||||||||||||||||||
| 403 | } | ||||||||||||||||||||||||||||||||
| 404 | else { | ||||||||||||||||||||||||||||||||
| 405 | # call poa | ||||||||||||||||||||||||||||||||
| 406 | 0 | $ovlp_seq = App::Fasops::Common::poa_consensus( | |||||||||||||||||||||||||||||||
| 407 | [ $ovlp_seq_contig, $ovlp_seq_anchor_1 ] ); | ||||||||||||||||||||||||||||||||
| 408 | } | ||||||||||||||||||||||||||||||||
| 409 | } | ||||||||||||||||||||||||||||||||
| 410 | else { | ||||||||||||||||||||||||||||||||
| 411 | # call poa | ||||||||||||||||||||||||||||||||
| 412 | 1 | $ovlp_seq = App::Fasops::Common::poa_consensus( | |||||||||||||||||||||||||||||||
| 413 | [ $ovlp_seq_contig, $ovlp_seq_anchor_1 ] ); | ||||||||||||||||||||||||||||||||
| 414 | } | ||||||||||||||||||||||||||||||||
| 415 | |||||||||||||||||||||||||||||||||
| 416 | # remove length of ovlp_len_120 from contig and anchor_1 | ||||||||||||||||||||||||||||||||
| 417 | 1 | substr $contig, -$ovlp_len_120, $ovlp_len_120, ""; | |||||||||||||||||||||||||||||||
| 418 | 1 | substr $seq_anchor_1, 0, $ovlp_len_120, ""; | |||||||||||||||||||||||||||||||
| 419 | |||||||||||||||||||||||||||||||||
| 420 | 1 | $contig .= $ovlp_seq . $seq_anchor_1; | |||||||||||||||||||||||||||||||
| 421 | } | ||||||||||||||||||||||||||||||||
| 422 | } | ||||||||||||||||||||||||||||||||
| 423 | else { | ||||||||||||||||||||||||||||||||
| 424 | 0 | my @spaces; | |||||||||||||||||||||||||||||||
| 425 | 0 | for my $long_read ( @{ $relation_of->{$pair}{long_reads} } ) { | |||||||||||||||||||||||||||||||
| 426 | |||||||||||||||||||||||||||||||||
| 427 | #@type AlignDB::IntSpan | ||||||||||||||||||||||||||||||||
| 428 | 0 | my $intspan_0 = $links_of->{$long_read}{$anchor_0}; | |||||||||||||||||||||||||||||||
| 429 | 0 | ▶ | next unless defined $intspan_0; | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 430 | |||||||||||||||||||||||||||||||||
| 431 | #@type AlignDB::IntSpan | ||||||||||||||||||||||||||||||||
| 432 | 0 | my $intspan_1 = $links_of->{$long_read}{$anchor_1}; | |||||||||||||||||||||||||||||||
| 433 | 0 | ▶ | next unless defined $intspan_1; | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 434 | |||||||||||||||||||||||||||||||||
| 435 | # reduce ends | ||||||||||||||||||||||||||||||||
| 436 | 0 | $intspan_0 = $intspan_0->trim( $opt->{border} ); | |||||||||||||||||||||||||||||||
| 437 | 0 | $intspan_1 = $intspan_1->trim( $opt->{border} ); | |||||||||||||||||||||||||||||||
| 438 | |||||||||||||||||||||||||||||||||
| 439 | 0 | my $intspan_space = $intspan_0->union($intspan_1)->holes; | |||||||||||||||||||||||||||||||
| 440 | 0 | ▶ | next if $intspan_space->is_empty; | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 441 | |||||||||||||||||||||||||||||||||
| 442 | 0 | push @spaces, $intspan_space->substr_span( $seq_of->{$long_read} ); | |||||||||||||||||||||||||||||||
| 443 | } | ||||||||||||||||||||||||||||||||
| 444 | |||||||||||||||||||||||||||||||||
| 445 | 0 | my $left_border = substr $contig, -$opt->{border}; | |||||||||||||||||||||||||||||||
| 446 | 0 | my $right_border = substr $seq_anchor_1, 0, $opt->{border}; | |||||||||||||||||||||||||||||||
| 447 | 0 | for my $s (@spaces) { | |||||||||||||||||||||||||||||||
| 448 | 0 | substr $s, 0, $opt->{border}, $left_border; | |||||||||||||||||||||||||||||||
| 449 | 0 | substr $s, -$opt->{border}, $opt->{border}, $right_border; | |||||||||||||||||||||||||||||||
| 450 | } | ||||||||||||||||||||||||||||||||
| 451 | |||||||||||||||||||||||||||||||||
| 452 | 0 | my $space_seq = App::Fasops::Common::poa_consensus( \@spaces ); | |||||||||||||||||||||||||||||||
| 453 | |||||||||||||||||||||||||||||||||
| 454 | # remove length of $opt->{border} from contig and anchor_1 | ||||||||||||||||||||||||||||||||
| 455 | 0 | substr $contig, -$opt->{border}, $opt->{border}, ""; | |||||||||||||||||||||||||||||||
| 456 | 0 | substr $seq_anchor_1, 0, $opt->{border}, ""; | |||||||||||||||||||||||||||||||
| 457 | |||||||||||||||||||||||||||||||||
| 458 | 0 | $contig .= $space_seq; | |||||||||||||||||||||||||||||||
| 459 | 0 | $contig .= $seq_anchor_1; | |||||||||||||||||||||||||||||||
| 460 | } | ||||||||||||||||||||||||||||||||
| 461 | } | ||||||||||||||||||||||||||||||||
| 462 | } | ||||||||||||||||||||||||||||||||
| 463 | |||||||||||||||||||||||||||||||||
| 464 | 0 | $contig .= "\n"; | |||||||||||||||||||||||||||||||
| 465 | 0 | $count++; | |||||||||||||||||||||||||||||||
| 466 | } | ||||||||||||||||||||||||||||||||
| 467 | |||||||||||||||||||||||||||||||||
| 468 | 0 | Path::Tiny::path( $opt->{outfile} )->spew($contig); | |||||||||||||||||||||||||||||||
| 469 | } | ||||||||||||||||||||||||||||||||
| 470 | |||||||||||||||||||||||||||||||||
| 471 | 11 | 1; | |||||||||||||||||||||||||||||||