+sub new_space
+{
+ # Martin A. Hansen, August 2009.
+
+ # Define a new search space if not previously
+ # defined. This occurs if align_two_seq() is
+ # called initially with only the sequences.
+
+ my ( $space, # search space
+ ) = @_;
+
+ # Returns nothing.
+
+ if ( not defined $space->{ 'Q_MAX' } )
+ {
+ $space->{ 'Q_MIN' } = 0;
+ $space->{ 'S_MIN' } = 0;
+ $space->{ 'Q_MAX' } = length( ${ $space->{ 'Q_SEQ' } } ) - 1,
+ $space->{ 'S_MAX' } = length( ${ $space->{ 'S_SEQ' } } ) - 1,
+ }
+}
+
+
+sub new_space_left
+{
+ # Martin A. Hansen, August 2009.
+
+ # Create a new search space between the beginning of
+ # the current search space and the best match.
+
+ my ( $best_match, # best match
+ $space, # search space
+ ) = @_;
+
+ # Returns hashref.
+
+ my ( $new_space );
+
+ if ( $best_match->{ 'Q_BEG' } - $space->{ 'Q_MIN' } >= 2 and $best_match->{ 'S_BEG' } - $space->{ 'S_MIN' } >= 2 )
+ {
+ $new_space = {
+ Q_SEQ => $space->{ 'Q_SEQ' },
+ S_SEQ => $space->{ 'S_SEQ' },
+ Q_MIN => $space->{ 'Q_MIN' },
+ Q_MAX => $best_match->{ 'Q_BEG' } - 1,
+ S_MIN => $space->{ 'S_MIN' },
+ S_MAX => $best_match->{ 'S_BEG' } - 1,
+ };
+ }
+
+ return wantarray ? %{ $new_space } : $new_space;
+}
+
+
+sub new_space_right
+{
+ # Martin A. Hansen, August 2009.
+
+ # Create a new search space between the best match
+ # and the end of the current search space.
+
+ my ( $best_match, # best match
+ $space, # search space
+ ) = @_;
+
+ # Returns hashref.
+
+ my ( $new_space );
+
+ if ( $space->{ 'Q_MAX' } - $best_match->{ 'Q_END' } >= 2 and $space->{ 'S_MAX' } - $best_match->{ 'S_END' } >= 2 )
+ {
+ $new_space = {
+ Q_SEQ => $space->{ 'Q_SEQ' },
+ S_SEQ => $space->{ 'S_SEQ' },
+ Q_MIN => $best_match->{ 'Q_END' } + 1,
+ Q_MAX => $space->{ 'Q_MAX' },
+ S_MIN => $best_match->{ 'S_END' } + 1,
+ S_MAX => $space->{ 'S_MAX' },
+ };
+ }
+
+ return wantarray ? %{ $new_space } : $new_space;
+}
+
+
+sub matches_select