Discovering dependencies between attributes in multi- attribute event sequences (multi-sequences), also known as synchronized multi-stream sequences, is an important prob- lem in many domains, including monitoring systems and molecular biology. Many real-life multi-sequences have a segmental structure, with segments of differing complexities of attribute dependencies, which reflects a changing nature of the dependencies over time and space. In this paper we propose a new approach for discovering dependencies in multi-sequences which considers a possible segmental na- ture of such dependencies and tries to describe the multi- sequences in probabilistic terms using Dynamic Bayesian Networks (DBN). To accurately quantify such changing de- pendencies, we segment the multi-sequence by fitting an op- timal DBN for each segment. We use the Bayesian Informa- tion Criterion (BIC) to select an optimal DBN structure and the number of segments of the multi-sequence.